Advertisement
najim

Untitled

Nov 16th, 2014
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<queue>
  4. #include<ctype.h>
  5. #include<ctype.h>
  6. #include<vector>
  7. #include<iostream>
  8. using namespace std;
  9. #define maxn 911*911
  10. #define maxc 26
  11. #define lowestChar 'a'
  12.  
  13. int ch[maxn][maxc];
  14. int val[maxn];
  15. int f[maxn];
  16. int cnt;
  17. int ans[maxn];
  18.  
  19. char str[1000010];
  20. char tmp[510];
  21.  
  22. /* ...... */
  23. vector<int>track[maxn];
  24. //vector<int>go[maxn];
  25. /* ...... */
  26.  
  27. void init()
  28. {
  29. cnt = 1;
  30. memset(ch[0],0,sizeof(ch[0]));
  31. memset(ans,0,sizeof(ans));
  32. for(int i=0;i<maxn;i++)
  33. {
  34. track[i].clear();
  35. //go[i].clear();
  36. }
  37. }
  38. void ac_insert_trie(char *s,int key)
  39. {
  40. int u = 0;
  41. while(*s)
  42. {
  43. int id = *s - lowestChar;
  44. if(ch[u][id] == 0)
  45. {
  46. memset(ch[cnt],0,sizeof(ch[cnt]));
  47. val[cnt] = 0;
  48. ch[u][id] = cnt++;
  49. }
  50. u = ch[u][id];
  51. s++;
  52. }
  53. val[u] = key;
  54. /* ...... */
  55. track[u].push_back(key);
  56. /* ...... */
  57. }
  58. void ac_get_fail()
  59. {
  60. queue<int> q;
  61. for(int c = 0; c < maxc; c++)
  62. {
  63. int u = ch[0][c];
  64. if(u)
  65. {
  66. f[u] = 0;
  67. q.push(u);
  68. }
  69. }
  70. while(!q.empty())
  71. {
  72. int r = q.front();
  73. q.pop();
  74. for(int c = 0; c < maxc; c++)
  75. {
  76. int u = ch[r][c];
  77. if(u)
  78. {
  79. q.push(u);
  80. int v = f[r];
  81. while(v && !ch[v][c]) v = f[v];
  82. f[u] = ch[v][c];
  83. }
  84. }
  85. }
  86. }
  87. void ac_find(int len)
  88. {
  89. int j = 0;
  90. for(int i = 0; i < len; i++)
  91. {
  92. int c = str[i] - lowestChar;
  93. while(j && !ch[j][c]) j = f[j];
  94. j = ch[j][c];
  95. int t = j;
  96. while(t && val[t])
  97. {
  98. /* ...... */
  99. for(int x=0;x<track[t].size();x++)
  100. {
  101. ans[track[t][x]]++;
  102. //go[track[t][x]].push_back(i);
  103. }
  104. /* ...... */
  105. t = f[t];
  106. }
  107. }
  108. }
  109.  
  110. int main()
  111. {
  112. int n;
  113. int kase,ks=0;
  114. scanf("%d",&kase);
  115. while(kase--)
  116. {
  117. scanf("%d",&n);
  118. init();
  119. scanf("%s",str);
  120. for(int i = 1; i <= n; i++)
  121. {
  122. scanf("%s",tmp);
  123. ac_insert_trie(tmp,i);
  124. }
  125. ac_get_fail();
  126. ac_find(strlen(str));
  127. printf("Case %d:\n",++ks);
  128. for(int i = 1; i <= n; i++)
  129. {
  130. printf("%d\n",ans[i]);
  131. }
  132. }
  133. return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement