fork download
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. using namespace std;
  6. const int MAX = 100005;
  7. const int SQRT = 300;
  8. int nxt[MAX][26], f[MAX], state[MAX], sz = 1;
  9. int insert(string &s)
  10. {
  11. int v = 0;
  12. for (int i = 0; i < (int)s.size(); i++)
  13. {
  14. if (nxt[v][s[i] - 'a'] == 0)
  15. nxt[v][s[i] - 'a'] = sz++;
  16. v = nxt[v][s[i] - 'a'];
  17. }
  18. return v;
  19. }
  20. int q[MAX];
  21. void aho()
  22. {
  23. int h = 0, t = 0;
  24. for (int i = 0; i < 26; i++)
  25. if (nxt[0][i])
  26. q[t++] = nxt[0][i];
  27. while (h < t)
  28. {
  29. int v = q[h++];
  30. for (int i = 0; i < 26; i++)
  31. if (nxt[v][i])
  32. {
  33. f[nxt[v][i]] = nxt[f[v]][i];
  34. q[t++] = nxt[v][i];
  35. }
  36. else
  37. nxt[v][i] = nxt[f[v]][i];
  38. }
  39. }
  40. vector<int> adj[MAX];
  41. int st[MAX], fi[MAX], cnt;
  42. void dfs(int v)
  43. {
  44. st[v] = cnt++;
  45. for (int i = 0; i < (int)adj[v].size(); i++)
  46. dfs(adj[v][i]);
  47. fi[v] = cnt;
  48. }
  49. int fen[MAX];
  50. void _add(int p, int val)
  51. {
  52. for (; p > 0; p -= p & -p)
  53. fen[p] += val;
  54. }
  55. void add(int l, int r, int val)
  56. {
  57. _add(r, val);
  58. _add(l, -val);
  59. }
  60. int get(int p)
  61. {
  62. int ans = 0;
  63. for (p++; p < MAX; p += p & -p)
  64. ans += fen[p];
  65. return ans;
  66. }
  67. struct query
  68. {
  69. int r, k, id, sign;
  70. query(int _r = 0, int _k = 0, int _id = 0, int _sign = 0)
  71. {
  72. r = _r;
  73. k = _k;
  74. id = _id;
  75. sign = _sign;
  76. }
  77. } que[2 * MAX];
  78. bool cmp(query x, query y)
  79. {
  80. return (x.r < y.r);
  81. }
  82. vector<query> qq[MAX];
  83. long long ps[MAX], ans[MAX];
  84. int sum[MAX], n;
  85. void pre(int v)
  86. {
  87. for (int i = 0; i < (int)adj[v].size(); i++)
  88. {
  89. int u = adj[v][i];
  90. pre(u);
  91. sum[v] += sum[u];
  92. }
  93. }
  94. string s[MAX];
  95. void solve(int id)
  96. {
  97. memset(sum, 0, sizeof(sum));
  98. int v = 0;
  99. for (int i = 0; i < (int)s[id].size(); i++)
  100. {
  101. v = nxt[v][s[id][i] - 'a'];
  102. sum[v]++;
  103. }
  104. pre(0);
  105. for (int i = 0; i < n; i++)
  106. ps[i + 1] = ps[i] + sum[state[i]];
  107. for (int i = 0; i < (int)qq[id].size(); i++)
  108. ans[qq[id][i].id] += qq[id][i].sign * ps[qq[id][i].r];
  109. }
  110. int main()
  111. {
  112. ios::sync_with_stdio(false);
  113. cin.tie(0);
  114. int q;
  115. cin >> n >> q;
  116. for (int i = 0; i < n; i++)
  117. {
  118. cin >> s[i];
  119. state[i] = insert(s[i]);
  120. }
  121. aho();
  122. for (int i = 1; i < sz; i++)
  123. adj[f[i]].push_back(i);
  124. dfs(0);
  125. sz = 0;
  126. for (int i = 0; i < q; i++)
  127. {
  128. int l, r, k;
  129. cin >> l >> r >> k;
  130. l--;
  131. k--;
  132. if (s[k].size() <= SQRT)
  133. {
  134. que[sz++] = query(r, k, i, 1);
  135. que[sz++] = query(l, k, i, -1);
  136. }
  137. else
  138. {
  139. qq[k].push_back(query(r, k, i, 1));
  140. qq[k].push_back(query(l, k, i, -1));
  141. }
  142. }
  143. for (int i = 0; i < n; i++)
  144. if (s[i].size() > SQRT)
  145. solve(i);
  146. sort(que, que + sz, cmp);
  147. int ptr = 0;
  148. for (int i = 0; i < sz; i++)
  149. {
  150. while (ptr < que[i].r)
  151. {
  152. add(st[state[ptr]], fi[state[ptr]], 1);
  153. ptr++;
  154. }
  155. int v = 0;
  156. for (int j = 0; j < (int)s[que[i].k].size(); j++)
  157. {
  158. v = nxt[v][s[que[i].k][j] - 'a'];
  159. ans[que[i].id] += que[i].sign * get(st[v]);
  160. }
  161. }
  162. for (int i = 0; i < q; i++)
  163. cout << ans[i] << "\n";
  164. return 0;
  165. }
  166.  
Runtime error #stdin #stdout 0s 23776KB
stdin
Standard input is empty
stdout
Standard output is empty