1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <queue>  5 #include <map>  6 #include <string>  7 #include <set>  8 using namespace std;  9  10 #define CHARSET 2 11 #define MAX_NODE 1010000 12  13 int T,N; 14 char inp[5000100]; 15  16 struct trieNode{ 17     int ch[CHARSET]; 18     int cnt; 19     //bool vis; 20 }; 21 trieNode trie[MAX_NODE]; 22 int ptr,fail[MAX_NODE]; 23  24 void init(){ 25     memset(fail,0,sizeof(fail)); 26     ptr = 0; 27     for(int i=0;i<CHARSET;i++){ 28         trie[0].ch[i] = -1; 29     } 30     trie[0].cnt = 0; 31     //trie[0].vis = false; 32 } 33  34 int newNode(){ 35     ptr++; 36     for(int i=0;i<CHARSET;i++){ 37         trie[ptr].ch[i] = -1; 38     } 39     trie[ptr].cnt = 0; 40     //trie[ptr].vis = false; 41     return ptr; 42 } 43  44 void insert(const char* str,int L){ 45 //    printf("insert:"); 46     int len = strlen(str); 47     int rt = 0; 48     L %= len; 49     for(int i=0;i<len;i++){ 50         //trie[rt].vis = true; 51         int id = str[(i+L)%len] -‘0‘; 52 //        printf("%d",id); 53         if(trie[rt].ch[id]==-1){ 54             trie[rt].ch[id] = newNode(); 55         } 56         rt = trie[rt].ch[id]; 57     } 58     //trie[rt].vis = true; 59     trie[rt].cnt = 1; 60 //    puts(""); 61 } 62  63 void build(){ 64     queue<int> q; 65     //trie[0].vis = false; 66     q.push(0); 67     fail[0] = -1; 68     while(!q.empty()){ 69         int t = q.front(); q.pop(); 70         for(int i=0;i<CHARSET;i++){ 71             int v = trie[t].ch[i]; 72             if( v==-1 ) continue; 73 //            if( trie[v].vis ){ 74 //                trie[v].vis = false; 75 //            } else continue; 76             int f = fail[t]; 77             while(f!=-1&&trie[f].ch[i]==-1){ 78                 f = fail[f]; 79             } 80             if(f==-1) fail[v] = 0; 81             else fail[v] = trie[f].ch[i]; 82             q.push(v); 83         } 84     } 85 } 86  87 int query(const char *str,int L){ 88 //    printf("query:"); 89     int res = 0; 90     int rt = 0; 91     int len = strlen(str); 92     L %= len; 93     for(int i=0;i<len;i++){ 94         int id = str[(i+L)%len] - ‘0‘; 95 //        printf("%d",id); 96         while(rt&&trie[rt].ch[id]==-1) rt = fail[rt]; 97         rt = trie[rt].ch[id]; 98  99         if(rt==-1){100             rt = 0;101             continue;102         }103 104         int now = rt;105         while(now!=-1){106             res += trie[now].cnt;107             now = fail[now];108         }109     }110 //    puts("");111     return res;112 }113 114 int main(){115 //    freopen("output.txt","w",stdout);116     scanf("%d",&T);117     for(int t=1;t<=T;t++){118         int L = 0;119         init();120         printf("Case #%d:\n",t);121         scanf("%d",&N);122         while(N--){123             scanf("%s",inp);124             if( inp[0]==‘+‘ ){125                 insert(inp+1,L);126             } else {127                 build();128                 int ans = query(inp+1,L);129                 L = ans;130                 printf("%d\n",ans);131             }132         }133     }134     return 0;135 }