本文共 2066 字，大约阅读时间需要 6 分钟。
AC自动机+DP
有点像GT考试，hh[i][j]表示第i为匹配到自动机上j号结点的方案数
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)14 #define re(i,l,r) for(int i=(l);i<=(r);i++)15 #define Clear(a,b) memset(a,b,sizeof(a))16 #define inout(x) printf("%d",(x))17 #define douin(x) scanf("%lf",&x)18 #define strin(x) scanf("%s",(x))19 #define LLin(x) scanf("%lld",&x)20 #define op operator21 #define CSC main22 typedef unsigned long long ULL;23 typedef const int cint;24 typedef long long LL;25 using namespace std;26 void inin(int &ret)27 {28 ret=0;int f=0;char ch=getchar();29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();31 ret=f?-ret:ret;32 }33 int n,m,ch[6060][26],pre[6060],hh[111][6060],v[6060],ed=1,last[6060];34 char s[1010];35 void add(char *s,int x)36 {37 int temp=1,len=strlen(s);38 re(i,0,len-1)39 {40 int c=s[i]-'A';41 if(!ch[temp][c])ch[temp][c]=++ed;42 temp=ch[temp][c];43 }44 v[temp]=x;45 }46 void getfail()47 {48 queue h;int k;49 h.push(1);50 while(!h.empty())51 {52 int x=h.front();h.pop();53 re(i,0,25)54 {55 if(!ch[x][i])continue;56 int vv=ch[x][i];57 h.push(vv);58 k=pre[x];59 while(!ch[k][i])k=pre[k];60 pre[vv]=ch[k][i];61 if(v[ch[k][i]])v[ch[x][i]]=v[ch[k][i]];62 last[vv]=v[pre[vv]]?pre[vv]:last[pre[vv]];63 }64 }65 }66 cint mod=10007;67 void dp(int x)68 {69 re(i,1,ed)70 {71 if(v[i]||!hh[x-1][i])continue;72 re(j,0,25)73 {74 int k=i;75 while(!ch[k][j])k=pre[k];76 (hh[x][ch[k][j]]+=hh[x-1][i])%=mod;77 }78 }79 }80 int main()81 {82 inin(n),inin(m);83 re(i,0,25)ch[0][i]=1;84 re(i,1,n)85 {86 strin(s);87 add(s,i);88 }89 getfail();90 hh[0][1]=1;91 re(i,1,m)dp(i);92 int ans1=0,ans2=1;93 re(i,1,m)ans2=ans2*26%mod;94 re(i,1,ed)if(!v[i])(ans1+=hh[m][i])%=mod;95 printf("%d",(ans2-ans1+mod)%mod);96 return 0;97 }
转载于:https://www.cnblogs.com/HugeGun/p/5226296.html