题目链接：

题意：

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

题解：

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

 

1 #include
      
        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
       
        =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\n",++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 }