hdu_3341_Lost's revenge(AC自动机+状态hashDP)

题意：

有n个模式串，一个标准串，现在让标准串重组，使得包含最多的模式串，可重叠，问重组后最多包含多少模式串

题解：

显然是AC自动机上的状态压缩DP，不过如果直接开40⁴*500的数组显示开不下，所以这样要将状态hash一下，然后再DP，因为这个字母加起来为40，所以状态数不超过15000，所以可以接受。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 
 5 const int AC_N=100*11,tyn=4;//数量乘串长,类型数
 6 struct AC_automation{
 7     int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot;
 8     inline int getid(char x){
 9         if(x=='A')return 0;
10         if(x=='C')return 1;
11         if(x=='G')return 2;
12         return 3;
13     }
14     void nw(){cnt[++tot]=0,fail[tot]=0;memset(tr[tot],0,sizeof(tr[tot]));}
15     void init(){tot=-1,fail[0]=-1,nw();}
16     void insert(char *s,int x=0){
17         for(int len=strlen(s),i=0,w;i<len;x=tr[x][w],i++)
18             if(!tr[x][w=getid(s[i])])nw(),tr[x][w]=tot;
19         cnt[x]++;//串尾标记
20     }
21     void build(int head=1,int tail=0){
22         for(int i=0;i<tyn;i++)if(tr[0][i])Q[++tail]=tr[0][i];
23         while(head<=tail)for(int x=Q[head++],i=0;i<tyn;i++)
24             if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q[++tail]=tr[x][i],cnt[tr[x][i]]+=cnt[tr[fail[x]][i]];
25             else tr[x][i]=tr[fail[x]][i];
26     }
27     
28 }AC;
29 
30 inline void up(int &a,int b){if(a<b)a=b;}
31 
32 char s[100];
33 int n,len,cnt,ic=0,na,nc,ng,nt;
34 int hsh[41][41][41][41],dp[15000][501];
35 
36 void fuck()
37 {
38     int ed=0,ans=0;
39     na=nc=ng=nt=0;
40     for(int i=0;s[i]!='';i++)if(s[i]=='A')na++;
41     else if(s[i]=='C')nc++;
42     else if(s[i]=='G')ng++;
43     else nt++;
44     F(i,0,na)F(j,0,nc)F(k,0,ng)F(l,0,nt)hsh[i][j][k][l]=ed++;
45     memset(dp,-1,sizeof(dp)),dp[0][0]=0;
46     F(i,0,na)F(j,0,nc)F(k,0,ng)F(l,0,nt)if(i+j+k+l!=0)
47     {
48         int x1=hsh[i][j][k][l],x2;
49         F(ii,0,AC.tot)F(jj,0,3)
50         {
51             if(jj==0&&i-1>=0)x2=hsh[i-1][j][k][l];
52             else if(jj==1&&j-1>=0)x2=hsh[i][j-1][k][l];
53             else if(jj==2&&k-1>=0)x2=hsh[i][j][k-1][l];
54             else if(jj==3&&l-1>=0)x2=hsh[i][j][k][l-1];
55             else continue;
56             if(dp[x2][ii]==-1)continue;
57             int now=AC.tr[ii][jj];
58             up(dp[x1][now],dp[x2][ii]+AC.cnt[now]);
59             up(ans,dp[x1][now]);
60         }
61     }
62     printf("Case %d: %d
",++ic,ans);
63 }
64 
65 int main()
66 {
67     while(scanf("%d",&n),n)
68     {
69         AC.init();
70         F(i,1,n)scanf("%s",s),AC.insert(s);
71         AC.build(),scanf("%s",s),fuck();
72     }
73     return 0;
74 }

View Code