想不出来啊 想不出来😟(全局变量数组开大还会RE。。。。。)
官方题解:**多模式串匹配的问题用 AC 自动机来解决。**首先用输入的这些串构建出 AC 自动机,然后用状压在 AC 自动机上对答案进行搜索。设 res[now][S][l],表示的意思是在自动机上当前节点为 now,状态是 S,已经匹配的长度为 l,有多少种方案数。用记忆化搜索将答案统计出来,就可以了。
问题
1) 为什么可以用状压dp解决呢
当此问题没有任何限制时,本题求的即为26的n次幂。对应代码
LL dfs(int l)
{
if(l==n){return 1;}
if(dp[l]) return dp[l];
LL ans=0;
for(int i=1;i<=26;i++){
ans=(ans+dfs(l+1))%mod;;
}
return dp[l]=ans;;
}
显然其中多算了一些不包含题目所给子串的答案,那么我们如何约束呢?
利用二进制存储信息的思想,把第i个串对应的Trie节点标记为 1<<(i-1)
所以只要我们在dfs答案时记录一个状态sta,当sta==1<<m-1时才计算答案即return1否则return 0 。这就可以完美的得到答案。
2)怎样记录当前的状态
当我们在Trie上建立过fail指针,并进行路径压缩后,那么一直枚举字母可以就看做一直在Trie上进行节点匹配。同时在build Trie 时把每个模式串结尾打上1)问的标记,然后我们再利用fail指针更新Trie上的每个节点所对应的状态
while(!q.empty()){
int p=q.front();q.pop();
is[p]=is[p]|is[fail[p]];//画重点
3) 状压dp的时间复杂度合理性
利用fail指针把每个可以成为模式串结尾的节点标记成对应的状态
具体看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=105;
const LL mod=1e9+7;
int fail[maxn+6],is[maxn+6],tot,trie[maxn][26],n,m;
LL dp[105][(1<<10)+10][30];
char s[maxn+6];
queue<int>q;
struct Ac_auto
{
void add(char *s,int id){
int len=strlen(s),p=0;
for(int i=0;i<len;i++){
int c=s[i]-'a';
if(!trie[p][c]){
trie[p][c]=++tot;
}
p=trie[p][c];
}
is[p]|=1<<id;
}
void build_fail(){
while(!q.empty()) q.pop();
for(int i=0;i<26;i++){
if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]);
}
while(!q.empty()){
int p=q.front();q.pop();
is[p]=is[p]|is[fail[p]];
for(int i=0;i<26;i++){
if(trie[p][i]){
fail[trie[p][i]]=trie[fail[p]][i];
q.push(trie[p][i]);
}
else
trie[p][i]=trie[fail[p]][i];
}
}
}
}ac;
LL dfs(int now,int state,int l)
{
if(l==n){
if(state==(1<<m)-1) return 1;
return 0;
}
if(dp[now][state][l]!=-1) return dp[now][state][l];
int ans=0,p;
for(int i=0;i<26;i++){
p=trie[now][i];
ans=(ans+dfs(p,is[p]|state,l+1))%mod;
}
dp[now][state][l]=ans;
return ans;
}
int main()
{
memset(dp,-1,sizeof dp);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%s",s);
ac.add(s,i-1);
}
ac.build_fail();
printf("%lld\n",dfs(0,0,0));
}