[HNOI2006]最短母串问题（AC自动机+状态压缩+bfs）
快要THUSC了，来水几道模板题吧。
这题其实是AC自动机模板。看到长度最短，首先就想到AC自动机。那么就直接暴力法来吧，把每个串建立在AC自动机上，建立fail指针，然后由于n<=12，可以把记录的状态压缩一下，就是压缩走到该节点出现了哪些状态，建立fail指针时也顺带更新一下。然后直接从根节点开始bfs，即可求出状态，复杂度O(26*2^n*Σ|S|)，注意内存是32MB，而我使用的空间复杂度是O(2^n*Σ|S|)，而开数组要开3个这么大的数组，这样通过计算需要34MB，所以将其中一个数组（vis数组）开成bool才能通过。
#include<bits/stdc++.h> using namespace std; const int N=610,M=5000; int n,cnt,tot,num,tim,ch[N][26],fail[N],st[N],a[N],ans[N*M],fa[N*M]; bool vis[N][M]; char str[N]; void build() { queue<int>q; for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]); while(!q.empty()) { int u=q.front();q.pop(); for(int i=0;i<26;i++) if(ch[u][i]) { fail[ch[u][i]]=ch[fail[u]][i]; st[ch[u][i]]|=st[ch[fail[u]][i]]; q.push(ch[u][i]); } else ch[u][i]=ch[fail[u]][i]; } } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",str); int u=0,len=strlen(str); for(int j=0;j<len;j++) { if(!ch[u][str[j]-'A'])ch[u][str[j]-'A']=++cnt; u=ch[u][str[j]-'A']; } st[u]|=1<<i-1; } build(); queue<int>q1,q2; q1.push(0),q2.push(0); while(!q1.empty()) { int u=q1.front(),S=q2.front(); q1.pop(),q2.pop(); if(S==(1<<n)-1) { while(tim)a[++num]=ans[tim],tim=fa[tim]; for(int i=num;i;i--)printf("%c",a[i]+'A'); return 0; } for(int i=0;i<26;i++) if(!vis[ch[u][i]][S|st[ch[u][i]]]) { vis[ch[u][i]][S|st[ch[u][i]]]=1; q1.push(ch[u][i]),q2.push(S|st[ch[u][i]]); fa[++tot]=tim,ans[tot]=i; } tim++; } }