题目链接：hdu_4787_GRE Words Revenge
题意：
总共有n个操作，2种操作。每行读入一个字符串。
1.如果字符串以+开头，此为单词（即模式串，不考虑重复）
2.如果字符串以？开头，此为文章（即文本串，查询在此之前的单词在文本串中出现的次数）
题解：
强制在线的AC自动机
贴个大牛的详细题解http://blog.csdn.net/no__stop/article/details/16823479
这样的带合并操作的AC自动机用第二种建树的方式比较方便
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int AC_N=1e5+,tyn=,M=5e6+;//数量乘串长,类型数
struct AC_automation{
int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot;
void nw(){cnt[++tot]=;memset(tr[tot],-,sizeof(tr[tot]));}
void init(){tot=-,fail[]=-,nw();}
void insert(char *s,int x=){
for(int i=,w;s[i];x=tr[x][w],i++)
if(tr[x][w=s[i]-'']==-)nw(),tr[x][w]=tot;
cnt[x]=;//串尾标记
}
void build(int head=,int tail=){
F(i,,)if(~tr[][i])Q[++tail]=tr[][i],fail[tr[][i]]=;
while(head<=tail){
for(int i=,x=Q[head++],p=-;i<tyn;i++)if(~tr[x][i]){
for(p=fail[x],fail[tr[x][i]]=;~p;p=fail[p])
if(~tr[p][i]){fail[tr[x][i]]=tr[p][i];break;}
Q[++tail]=tr[x][i];
}
}
}
int ask(char *s,int ans=){
for(int w,i=,x=,j;s[i];i++){
while(tr[x][w=s[i]-'']==-&&x)x=fail[x];
x=tr[x][w],x=(~x)?x:,j=x;
while(j){if(cnt[j])ans++;j=fail[j];}
}
return ans;
} }a,b; char s[M],tps[M];
int t,n,an,sqr=,bcnt; void dfs(int r1,int r2)//将b中以r2为根结点的树合并到a中以r1为根结点的树中
{
F(i,,)if(~b.tr[r2][i])
{
if(a.tr[r1][i]==-)a.nw(),a.tr[r1][i]=a.tot;
a.cnt[a.tr[r1][i]]|=b.cnt[b.tr[r2][i]];
dfs(a.tr[r1][i],b.tr[r2][i]);
}
} void join(){dfs(,),b.init(),a.build();}//将b合并到a中 void decrypt()
{
int len=strlen(s);
int k=an%(len-),ed=;
F(i,,len-)tps[i]=s[i];
F(i,k+,len-)s[++ed]=tps[i];
F(i,,k)s[++ed]=tps[i];
} int main()
{
scanf("%d",&t);
F(ic,,t)
{
printf("Case #%d:\n",ic);
scanf("%d",&n);
a.init(),b.init(),an=bcnt=;
F(i,,n)
{
scanf("%s",s),decrypt();
if(s[]=='+')
{
b.insert(s+),b.build(),bcnt++;
if(bcnt>sqr)join();
}else printf("%d\n",(an=a.ask(s+)+b.ask(s+)));
}
}
return ;
}