1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4  5 const int AC_N=1e5+7,tyn=2,M=5e6+10;//数量乘串长,类型数 6 struct AC_automation{ 7     int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot; 8     void nw(){cnt[++tot]=0;memset(tr[tot],-1,sizeof(tr[tot]));} 9     void init(){tot=-1,fail[0]=-1,nw();}10     void insert(char *s,int x=0){11         for(int i=0,w;s[i];x=tr[x][w],i++)12             if(tr[x][w=s[i]-‘0‘]==-1)nw(),tr[x][w]=tot;13         cnt[x]=1;//串尾标记14     }15     void build(int head=1,int tail=0){16         F(i,0,1)if(~tr[0][i])Q[++tail]=tr[0][i],fail[tr[0][i]]=0;17         while(head<=tail){18             for(int i=0,x=Q[head++],p=-1;i<tyn;i++)if(~tr[x][i]){19                 for(p=fail[x],fail[tr[x][i]]=0;~p;p=fail[p])20                     if(~tr[p][i]){fail[tr[x][i]]=tr[p][i];break;}21                 Q[++tail]=tr[x][i];22             }23         }24     }25     int ask(char *s,int ans=0){26         for(int w,i=0,x=0,j;s[i];i++){27             while(tr[x][w=s[i]-‘0‘]==-1&&x)x=fail[x];28             x=tr[x][w],x=(~x)?x:0,j=x;29             while(j){if(cnt[j])ans++;j=fail[j];}30         }31         return ans;32     }33     34 }a,b;35 36 char s[M],tps[M];37 int t,n,an,sqr=2000,bcnt;38 39 void dfs(int r1,int r2)//将b中以r2为根结点的树合并到a中以r1为根结点的树中40 {41     F(i,0,1)if(~b.tr[r2][i])42     {43         if(a.tr[r1][i]==-1)a.nw(),a.tr[r1][i]=a.tot;44         a.cnt[a.tr[r1][i]]|=b.cnt[b.tr[r2][i]];45         dfs(a.tr[r1][i],b.tr[r2][i]);46     }47 }48 49 void join(){dfs(0,0),b.init(),a.build();}//将b合并到a中50 51 void decrypt()52 {53     int len=strlen(s);54     int k=an%(len-1),ed=0;55     F(i,1,len-1)tps[i]=s[i];56     F(i,k+1,len-1)s[++ed]=tps[i];57     F(i,1,k)s[++ed]=tps[i];58 }59 60 int main()61 {62     scanf("%d",&t);63     F(ic,1,t)64     {65         printf("Case #%d:\n",ic);66         scanf("%d",&n);67         a.init(),b.init(),an=bcnt=0;68         F(i,1,n)69         {70             scanf("%s",s),decrypt();71             if(s[0]==‘+‘)72             {73                 b.insert(s+1),b.build(),bcnt++;74                 if(bcnt>sqr)join();75             }else printf("%d\n",(an=a.ask(s+1)+b.ask(s+1)));76         }77     }78     return 0;79 }