建立两个AC自动机，每次在小自动机上插入并且暴力重建，当小自动机的点数超过阈值时就把小自动机合并到大自动机上，暴力重建大自动机。注意因为要经常插入重建，需要区分trie树的边和AC自动机上补出来的边。
经过测试，阈值取 1000 比较快。但是数据比较水，所以阈值取 0 或者总串长
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
const int lim=0,maxn=100010,maxl=10000010;
int que[maxn];
struct acautomaton
{int trie[maxn][2],trans[maxn][2],fail[maxn],tag[maxn],num[maxn],tot;void clear(){for (int i=0;i<=tot;i++){for (int j=0;j<2;j++)trie[i][j]=trans[i][j]=0;tag[i]=fail[i]=num[i]=0;}tot=0;}int find(char *s,int l){int p=0;for (int i=0;i<l;i++)if (!trie[p][s[i]-'0']) return 0;else p=trie[p][s[i]-'0'];return tag[p];}void ins(char *s,int l){int p=0;for (int i=0;i<l;i++){if (!trie[p][s[i]-'0']) trie[p][s[i]-'0']=++tot;p=trie[p][s[i]-'0'];}tag[p]=1;}void init(){int hd=1,tl=0,u;for (int i=0;i<2;i++)if (trie[0][i]){trans[0][i]=trie[0][i];que[++tl]=trie[0][i];}while (hd<=tl){u=que[hd++];num[u]=tag[u]+num[fail[u]];for (int i=0;i<2;i++)if (trie[u][i]){trans[u][i]=trie[u][i];que[++tl]=trie[u][i];fail[trie[u][i]]=trans[fail[u]][i];}else trans[u][i]=trans[fail[u]][i];}}LL qry(char *s,int l){int p=0;LL ret=0;for (int i=0;i<l;i++){p=trans[p][s[i]-'0'];ret+=num[p];}return ret;}
}big,small;
void dfs(int &u,int v)
{if (!u) u=++big.tot;if (small.tag[v]) big.tag[u]=1;for (int i=0;i<2;i++)if (small.trie[v][i])dfs(big.trie[u][i],small.trie[v][i]);
}
void merge()
{for (int i=0;i<2;i++)if (small.trie[0][i])dfs(big.trie[0][i],small.trie[0][i]);
}
char s[maxl];
void solve()
{LL last=0;int p,q,l;big.clear();small.clear();scanf("%d",&q);while (q--){scanf("%s",s+1);l=strlen(s+1);for (int i=2;i<=l;i++) s[l+i-1]=s[i];p=last%(l-1)+2;if (s[1]=='+'){if (small.find(s+p,l-1)||big.find(s+p,l-1)) continue;small.ins(s+p,l-1);if (small.tot>lim){merge();big.init();small.clear();}else small.init();}else printf("%I64d\n",last=small.qry(s+p,l-1)+big.qry(s+p,l-1));}
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;scanf("%d",&T);for (int K=1;K<=T;K++){printf("Case #%d:\n",K);solve();}
}