fork download
  1. //tonynater - SPOJ 2013
  2.  
  3. #include <algorithm>
  4. #include <bitset>
  5. #include <cassert>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <fstream>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <string.h>
  22.  
  23. using namespace std;
  24.  
  25. #define sz(x) ((int) x.size())
  26.  
  27. typedef long double ld;
  28. typedef long long ll;
  29. typedef pair<int, int> pii;
  30.  
  31. const double pi = acos(-1);
  32. const double tau = 2*pi;
  33. const double epsilon = 1e-6;
  34.  
  35. const int MAX_M = 100100;
  36. const int MAX_N = 1100;
  37. const int MAX_WORD = 1100;
  38. const int MAX_AHO = 800100;
  39. const int MAX_LETTERS = 63;
  40. const int REDUCTION = 1;
  41.  
  42. char M[MAX_M];
  43.  
  44. int N;
  45.  
  46. bool isPresent[MAX_N];
  47. vector<int> repeats[MAX_N];
  48.  
  49. int lett(char c)
  50. {
  51. if('a' <= c && c <= 'z') return 1+c-'a';
  52. else if('A' <= c && c <= 'Z') return 1+26+c-'A';
  53. else return 1+52+c-'0';
  54. }
  55.  
  56. struct node
  57. {
  58. int val;
  59.  
  60. int terminal;
  61.  
  62. int parent;
  63. int children[MAX_LETTERS];
  64.  
  65. int fail;
  66.  
  67. node()
  68. {
  69. val = 0;
  70. terminal = 0;
  71. parent = 0;
  72. memset(children, 0, sizeof(children));
  73. fail = 0;
  74. }
  75. };
  76.  
  77. node aho[MAX_AHO/REDUCTION]; int sz;
  78.  
  79. char curWord[MAX_WORD]; int cwIdx;
  80. void add_word()
  81. {
  82. int wLen = strlen(curWord);
  83.  
  84. int idx = 1, pos = 0;
  85. while(true)
  86. {
  87. if(pos == wLen)
  88. {
  89. if(aho[idx].terminal == 0) aho[idx].terminal = cwIdx++;
  90. else repeats[aho[idx].terminal].push_back(cwIdx++);
  91.  
  92. break;
  93. }else if(aho[idx].children[lett(curWord[pos])] != 0) idx = aho[idx].children[lett(curWord[pos])];
  94. else
  95. {
  96. aho[idx].children[lett(curWord[pos])] = sz;
  97. aho[sz].val = lett(curWord[pos]);
  98. aho[sz].parent = idx;
  99.  
  100. idx = sz++;
  101. }
  102.  
  103. ++pos;
  104. }
  105. }
  106.  
  107. int fail(int idx, int val)
  108. {
  109. while(true)
  110. {
  111. if(aho[idx].children[val] != 0) return aho[idx].children[val];
  112. else if(idx == 1) return 1;
  113. idx = aho[idx].fail;
  114. }
  115. }
  116.  
  117. void build_fails()
  118. {
  119. queue<int> q;
  120. q.push(1);
  121.  
  122. while(!q.empty())
  123. {
  124. int u = q.front();
  125. q.pop();
  126.  
  127. for(int i = 0; i < MAX_LETTERS; i++)
  128. if(aho[u].children[i] != 0)
  129. {
  130. if(u == 1) aho[aho[u].children[i]].fail = 1;
  131. else aho[aho[u].children[i]].fail = fail(aho[u].fail, i);
  132.  
  133. q.push(aho[u].children[i]);
  134. }
  135. }
  136. }
  137.  
  138. int main (int argc, const char * argv[])
  139. {
  140. scanf("%s", M);
  141. scanf("%d", &N);
  142.  
  143. int mLen = strlen(M);
  144. for(int r = 1; r <= REDUCTION; r++)
  145. {
  146. memset(isPresent, 0, sizeof(isPresent));
  147. for(int i = 0; i < MAX_N; i++)
  148. repeats[i].clear();
  149. memset(aho, 0, sizeof(aho));
  150. sz = 2;
  151. cwIdx = 1;
  152.  
  153. for(int i = N*(r-1)/REDUCTION; i < N*r/REDUCTION; i++)
  154. {
  155. scanf("%s", curWord);
  156.  
  157. add_word();
  158. }
  159.  
  160. build_fails();
  161.  
  162. for(int i = 0, idx = 1; i < mLen; i++)
  163. {
  164. idx = fail(idx, lett(M[i]));
  165.  
  166. int curIdx = idx;
  167. while(aho[curIdx].terminal != 0)
  168. {
  169. isPresent[aho[curIdx].terminal] = true;
  170. aho[curIdx].terminal = 0;
  171. curIdx = aho[curIdx].fail;
  172. }
  173. }
  174.  
  175. for(int i = 1; i <= (N*r/REDUCTION)-N*(r-1)/REDUCTION; i++)
  176. for(int j = 0; j < sz(repeats[i]); j++)
  177. isPresent[repeats[i][j]] = true;
  178.  
  179. for(int i = 1; i <= (N*r/REDUCTION)-N*(r-1)/REDUCTION; i++)
  180. if(isPresent[i]) cout << "Y\n";
  181. else cout << "N\n";
  182. }
  183.  
  184. return 0;
  185. }
  186.  
Success #stdin #stdout 0.21s 212992KB
stdin
abghABCDE
2
abAB
ab
stdout
N
Y