Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<string.h>
- #include<queue>
- #include<ctype.h>
- #include<ctype.h>
- #include<vector>
- #include<iostream>
- using namespace std;
- #define maxn 911*911
- #define maxc 26
- #define lowestChar 'a'
- int ch[maxn][maxc];
- int val[maxn];
- int f[maxn];
- int cnt;
- int ans[maxn];
- char str[1000010];
- char tmp[510];
- /* ...... */
- vector<int>track[maxn];
- //vector<int>go[maxn];
- /* ...... */
- void init()
- {
- cnt = 1;
- memset(ch[0],0,sizeof(ch[0]));
- memset(ans,0,sizeof(ans));
- for(int i=0;i<maxn;i++)
- {
- track[i].clear();
- //go[i].clear();
- }
- }
- void ac_insert_trie(char *s,int key)
- {
- int u = 0;
- while(*s)
- {
- int id = *s - lowestChar;
- if(ch[u][id] == 0)
- {
- memset(ch[cnt],0,sizeof(ch[cnt]));
- val[cnt] = 0;
- ch[u][id] = cnt++;
- }
- u = ch[u][id];
- s++;
- }
- val[u] = key;
- /* ...... */
- track[u].push_back(key);
- /* ...... */
- }
- void ac_get_fail()
- {
- queue<int> q;
- for(int c = 0; c < maxc; c++)
- {
- int u = ch[0][c];
- if(u)
- {
- f[u] = 0;
- q.push(u);
- }
- }
- while(!q.empty())
- {
- int r = q.front();
- q.pop();
- for(int c = 0; c < maxc; c++)
- {
- int u = ch[r][c];
- if(u)
- {
- q.push(u);
- int v = f[r];
- while(v && !ch[v][c]) v = f[v];
- f[u] = ch[v][c];
- }
- }
- }
- }
- void ac_find(int len)
- {
- int j = 0;
- for(int i = 0; i < len; i++)
- {
- int c = str[i] - lowestChar;
- while(j && !ch[j][c]) j = f[j];
- j = ch[j][c];
- int t = j;
- while(t && val[t])
- {
- /* ...... */
- for(int x=0;x<track[t].size();x++)
- {
- ans[track[t][x]]++;
- //go[track[t][x]].push_back(i);
- }
- /* ...... */
- t = f[t];
- }
- }
- }
- int main()
- {
- int n;
- int kase,ks=0;
- scanf("%d",&kase);
- while(kase--)
- {
- scanf("%d",&n);
- init();
- scanf("%s",str);
- for(int i = 1; i <= n; i++)
- {
- scanf("%s",tmp);
- ac_insert_trie(tmp,i);
- }
- ac_get_fail();
- ac_find(strlen(str));
- printf("Case %d:\n",++ks);
- for(int i = 1; i <= n; i++)
- {
- printf("%d\n",ans[i]);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement