这个题目做得泪牛满面。
题目为给你若干串，有的表示添加一个串，有的表示询问一个串有多少个字串为前面出现过的串。
题目一看就知道肯定是AC自动机（不过后缀自动机也是可以的）
但是细想就会发现AC自动机好像不支持在线修改。如果你每次读入一个串就重构一次AC自动机的话，那么时间复杂度达到了N^2，肯定会T的。
于是就产生了一种奇葩的解法。
搞两个自动机，一个自动机为大的自动机，一个自动机为小的自动机（用于缓冲）。每次我都只把字符串加入到小的自动机里面并且重构小自动机，当小自动机的容量超过了sqrt(L)的时候，我们把小自动机合并到大自动机上，这样算下来时间复杂度为O(L*sqrt(L))，每次询问的答案就是大小自动机上查询答案的和，好像是可以AC的。
但是问题来了，怎么合并两个自动机呢？
其实很简单，自动机相对于字典树来说有什么区别呢？一个是tire树，一个是tire图，自动机多了fail指针还多了一些新建立的next指针。所以我们只要把这些多余的指针去掉，然后对小字典树做一次搜索就可以吧两个字典树合并了。然后重构了一次大自动机，小自动机清空，就可以了。
总的时间复杂度有点勉强，不过算下来10^5好像理论上来说也是可以过的。
赞一个，题目出的太好了。
不过听说还有用后缀自动机做，并且用动态树来维护的。不明觉厉啊。求神犇指点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 100050
using namespace std;
int next[2][maxn][2],has[2][maxn][2],tag[2][maxn],sum[2][maxn],fail[2][maxn],N[2];
char s0[50*maxn],s[50*maxn];
int qx[maxn],qy[maxn],tq;
int ans,n,t;
int add(int x)
{
N[x]++;
next[x][N[x]][0]=next[x][N[x]][1]=0;
has[x][N[x]][0]=has[x][N[x]][1]=0;
tag[x][N[x]]=0;
sum[x][N[x]]=0;
fail[x][N[x]]=0;
return N[x];
}
void init(int x)
{
N[x]=-1;
N[x]=add(x);
}
void initall()
{
ans=0;
init(0),init(1);
}
void getstring()
{
scanf("%s",s0);
int L=strlen(s0)-1,cur=0;
for (int i=ans%L+1; s0[i]; i++) s[cur]=s0[i],cur++;
for (int i=1; i<=ans%L; i++) s[cur]=s0[i],cur++;
s[L]=0;
}
void destory(int x)
{
for (int i=0; i<=N[x]; i++)
{
fail[x][i]=0;
for (int j=0; j<2; j++)
if (has[x][i][j]==0) next[x][i][j]=0;
}
}
void insert()
{
int cur=0,tep;
for (int i=0; s[i]; i++)
{
tep=s[i]-'0';
if (next[1][cur][tep]==0)
{
next[1][cur][tep]=add(1);
has[1][cur][tep]=1;
}
cur=next[1][cur][tep];
}
tag[1][cur]=1;
}
void union01()
{
int cur=1;
qx[1]=qy[1]=0;
while (cur>0)
{
int xx=qx[cur],yy=qy[cur];
if (tag[1][yy]) tag[0][xx]=1;
cur--;
for (int i=0; i<2; i++)
{
if (next[1][yy][i])
{
if (next[0][xx][i]==0)
{
next[0][xx][i]=add(0);
has[0][xx][i]=1;
}
cur++;
qx[cur]=next[0][xx][i];
qy[cur]=next[1][yy][i];
}
}
}
}
void AC_build(int x)
{
for (int i=0; i<=N[x]; i++) sum[x][i]=tag[x][i];
queue<int> Q;
int cur,child;
Q.push(0);
while (!Q.empty())
{
cur=Q.front(),Q.pop();
for (int i=0; i<2; i++)
{
child=next[x][cur][i];
if (child)
{
Q.push(child);
if (cur==0) fail[x][child]=0;
else
{
fail[x][child]=next[x][fail[x][cur]][i];
sum[x][child]+=sum[x][fail[x][child]];
}
}
else next[x][cur][i]=next[x][fail[x][cur]][i];
}
}
}
int query(int x)
{
int cur=0,tep,tot=0;
for (int i=0; s[i]; i++)
{
tep=s[i]-'0';
cur=next[x][cur][tep];
tot+=sum[x][cur];
}
return tot;
}
bool find(int x)
{
int cur=0,tep;
for (int i=0; s[i]; i++)
{
tep=s[i]-'0';
if (has[x][cur][tep]) cur=next[x][cur][tep];
else return false;
}
if (tag[x][cur]==0) return false;
return true;
}
int main()
{
int cas=0;
scanf("%d",&t);
while (t--)
{
printf("Case #%d:
",++cas);
initall();
scanf("%d",&n);
while (n--)
{
getstring();
if (s0[0]=='+')
{
if (find(1) || find(0)) continue;
destory(1);
insert();//insert s to trie 1
if (N[1]>=1000)
{
destory(0);
union01();
AC_build(0);
init(1);
}
else AC_build(1);
}
else if (s0[0]=='?')
{
ans=query(0)+query(1);
printf("%d
",ans);
}
}
}
return 0;
}