Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.79 KB | None | 0 0
  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstring>
  4. #include <bitset>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. const int MAXR = 105;
  10. const int MAXN = 5005;
  11. const int MAXL = 30;
  12. const int MAXK = 4;
  13.  
  14. struct Trie
  15. {
  16. //int iEnd;
  17. int iEnd;
  18. //vector <int> v;
  19. int mask[MAXK];
  20. Trie* child[MAXL];
  21. Trie* nv, *openLink;
  22. };
  23.  
  24. void init(Trie* &temp)
  25. {
  26. //printf("DSA");
  27. temp = new Trie();
  28. temp->iEnd = -1;
  29. for(int i = 0; i < MAXL; i++)
  30. {
  31. temp->child[i] = nullptr;
  32. }
  33. temp->nv = nullptr; temp->openLink = nullptr;
  34. }
  35.  
  36. Trie* root;
  37. int n, m, r, c;
  38. char str1[MAXR][MAXR];
  39. char str2[MAXN][MAXN];
  40.  
  41. void add_word(Trie* &tree, int num, int f, int temp)
  42. {
  43. //printf("%d %d\n", str1[temp][f], num);
  44. if(temp == r)
  45. {
  46. //if(tree->iEnd == -1)
  47. //tree->v.push_back(num);
  48. int mask = num / 30;
  49. int pos = num % 30;
  50. tree->mask[mask] |= (1 << pos);
  51. //printf("DSA");
  52. tree->iEnd = num;
  53. //tree->iEnd = num;
  54. }
  55. else
  56. {
  57. //printf("DSA");
  58. //printf("%d\n", t[0]);
  59. if(tree->child[str1[temp][f]] == nullptr)
  60. {
  61. init(tree->child[str1[temp][f]]);
  62. }
  63. add_word(tree->child[str1[temp][f]], num, f, temp + 1);
  64. }
  65. }
  66.  
  67. void read_input()
  68. {
  69. scanf("%d %d", &r, &c);
  70.  
  71. for(int i = 0; i < r; i++)
  72. {
  73. scanf("%s", str1[i]);
  74. }
  75. for(int i = 0; i < r; i++)
  76. {
  77. for(int j = 0; j < c; j++)
  78. {
  79. str1[i][j] -= 'a';
  80. }
  81. }
  82. //printf("DSA");
  83. init(root);
  84. for(int i = 0; i < c; i++)
  85. {
  86. add_word(root, i, i, 0);
  87. }
  88.  
  89. scanf("%d %d", &n, &m);
  90. for(int i = 0; i < n; i++)
  91. {
  92. scanf("%s", str2[i]);
  93. }
  94. for(int i = 0; i < n; i++)
  95. {
  96. for(int j = 0; j < m; j++)
  97. {
  98. str2[i][j] -= 'a';
  99. }
  100. }
  101. }
  102.  
  103. void pre_links()
  104. {
  105. queue <Trie*> q;
  106.  
  107. root->nv = root;
  108.  
  109. for(int i = 0; i < MAXL; i++)
  110. {
  111. if(root->child[i] != nullptr)
  112. {
  113. root->child[i]->nv = root;
  114. q.push(root->child[i]);
  115. }
  116. }
  117.  
  118. while(!q.empty())
  119. {
  120. Trie* v = q.front(); q.pop();
  121.  
  122. for(int x = 0; x < MAXL; x++)
  123. {
  124. if(v->child[x] != nullptr)
  125. {
  126. Trie* w = v->child[x];
  127. q.push(w);
  128. Trie* vw = v->nv;
  129.  
  130. while(vw->child[x] == nullptr && vw != root)
  131. {
  132. vw = vw->nv;
  133. }
  134. if(vw->child[x] != nullptr)
  135. {
  136. w->nv = vw->child[x];
  137. }
  138. else
  139. {
  140. w->nv = root;
  141. }
  142. if(w->nv->iEnd != -1)
  143. {
  144. w->openLink = w->nv;
  145. }
  146. else if(w->nv->openLink != nullptr)
  147. {
  148. w->openLink = w->nv->openLink;
  149. }
  150. }
  151. }
  152. }
  153. }
  154.  
  155. int ans;
  156. int o;
  157. int current[2][MAXN][MAXK];
  158.  
  159. void report_end(int masks[MAXK], int row)
  160. {
  161. int temp = (current[o ^ 1][row][0] << 1) & masks[0];
  162. current[o][row][0] |= temp;
  163. for(int i = 0; i < MAXK; i++)
  164. {
  165. temp = (current[o ^ 1][row][i] << 1) & masks[i];
  166. current[o][row][i] |= temp;
  167.  
  168. if(current[o ^ 1][row][i - 1] & (1 << 29))
  169. {
  170. current[o][row][i] |= 1;
  171. }
  172. }
  173.  
  174. //printf("%d %d\n", masks[0], row);
  175. //cout << bitset<2>(current[o ^ 1][row][0]) << "\n";
  176.  
  177. int mask = (c - 1) / 30;
  178. int pos = (c - 1) % 30;
  179. //printf("%d\n", current[o][row][2]);
  180. if(current[o][row][mask] & (1 << pos))
  181. {
  182. ans++;
  183. }
  184. if(masks[0] & 1)
  185. {
  186. //printf("DSA\n");
  187. current[o][row][0] |= 1;
  188. }
  189. //printf("%d %d %d\n", nd, temp, row);
  190. /*int z = 5;
  191. for(int i = z - 1; i >= 0; i--)
  192. {
  193. //printf("%d\n", z);
  194. int nd = 5;
  195. if(nd == 0)
  196. {
  197. //printf("%d %d %d\n", nd, row, temp);
  198. current[row][nd] = temp;
  199. if(nd == c - 1)
  200. {
  201. ans++;
  202. }
  203. }
  204. int prev = current[row][nd - 1];
  205. //printf("%d %d %d %d\n", nd, row, temp, prev);
  206. if(temp - prev == 1 && prev != -1)
  207. {
  208. if(nd == c - 1)
  209. {
  210. ans++;
  211. }
  212. current[row][nd] = temp;
  213. }
  214. }*/
  215. }
  216.  
  217. void full_ac(int coll)
  218. {
  219. int i = 0;
  220. Trie* w = root;
  221. Trie* w1;
  222. do
  223. {
  224. w1 = w->child[str2[i][coll]];
  225.  
  226. while(w1 != nullptr)
  227. {
  228. if(w1->iEnd != -1)
  229. {
  230. report_end(w1->mask, i);
  231. }
  232. if(w1->openLink != nullptr)
  233. {
  234. if(w1->openLink->iEnd != -1)
  235. {
  236. report_end(w1->openLink->mask, i);
  237. }
  238. }
  239.  
  240. w = w1;
  241. i++;
  242. if(i >= n)
  243. {
  244. break;
  245. }
  246.  
  247. w1 = w->child[str2[i][coll]];
  248. }
  249.  
  250. if(w != root)
  251. {
  252. w = w->nv;
  253. }
  254. else
  255. {
  256. i++;
  257. }
  258. }while(i < n);
  259. }
  260.  
  261. bool temp[MAXR];
  262.  
  263. void solve()
  264. {
  265. //memset(current, -1, sizeof(current));
  266. for(int i = 0; i < m; i++)
  267. {
  268. full_ac(i);
  269. for(int j = 0; j < n; j++)
  270. {
  271. for(int z = 0; z < MAXK; z++)
  272. {
  273. current[o ^ 1][j][z] = 0;
  274. }
  275. }
  276. o ^= 1;
  277. }
  278. printf("%d\n", ans);
  279. }
  280.  
  281. int main()
  282. {
  283. read_input();
  284. pre_links();
  285. solve();
  286.  
  287. return 0;
  288. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement