fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 5e4 + 42, logn = 20, sigma = 26;
  6.  
  7. string s[maxn];
  8.  
  9. struct suffix_automaton
  10. {
  11. vector<int> len, link, fpos, lpos, left, right, ans, max, cnt, st;
  12. vector<vector<int>> to;
  13. vector<vector<int>> up;
  14. string s;
  15. int sz, last;
  16.  
  17. void clear()
  18. {
  19. up.clear();
  20. to.clear();
  21. len.clear();
  22. link.clear();
  23. fpos.clear();
  24. lpos.clear();
  25. cnt.clear();
  26. st.clear();
  27. s.clear();
  28. }
  29.  
  30. void reserve(int n)
  31. {
  32. up.reserve(n);
  33. to.reserve(n);
  34. len.reserve(n);
  35. link.reserve(n);
  36. fpos.reserve(n);
  37. lpos.reserve(n);
  38. cnt.reserve(n);
  39. st.reserve(n);
  40. s.reserve(n);
  41. left.reserve(n);
  42. right.reserve(n);
  43. ans.reserve(n);
  44. max.reserve(n);
  45. }
  46.  
  47. int make_state(vector<int> new_to = vector<int>(sigma + 1), int new_link = 0, int new_fpos = 0, int new_len = 0)
  48. {
  49. to.push_back(new_to);
  50. link.push_back(new_link);
  51. fpos.push_back(new_fpos);
  52. len.push_back(new_len);
  53. lpos.push_back(new_fpos);
  54. left.push_back(0);
  55. right.push_back(0);
  56. ans.push_back(0);
  57. max.push_back(0);
  58. cnt.push_back(0);
  59. up.push_back(vector<int>(logn));
  60. return sz++;
  61. }
  62.  
  63. void add_letter(char c)
  64. {
  65. s += c;
  66. int p = last;
  67. last = make_state(vector<int>(sigma + 1), 0, len[p] + 1, len[p] + 1);
  68. st.push_back(last);
  69. cnt[last] = 1;
  70. for(; to[p][c] == 0; p = link[p])
  71. to[p][c] = last;
  72. if(to[p][c] == last)
  73. return;
  74. int q = to[p][c];
  75. if(len[q] == len[p] + 1)
  76. {
  77. link[last] = q;
  78. return;
  79. }
  80. int cl = make_state(to[q], link[q], fpos[q], len[p] + 1);
  81. link[last] = link[q] = cl;
  82. for(; to[p][c] == q; p = link[p])
  83. to[p][c] = cl;
  84. }
  85.  
  86. void build(string s)
  87. {
  88. make_state();
  89. int n = s.size();
  90. reserve(4 * n);
  91.  
  92. for(auto c: s)
  93. add_letter(c);
  94.  
  95. int mx_len[n]; // kill states like "X#Y"
  96. memset(mx_len, 0, sizeof(mx_len));
  97. int count = 0;
  98. for(int i = 0; i < n; i++)
  99. {
  100. mx_len[i] = count++;
  101. if(s[i] == sigma)
  102. count = 1;
  103. }
  104. for(int state = 1; state < sz; state++)
  105. {
  106. if(len[link[state]] < mx_len[fpos[state] - 1] && len[state] > mx_len[fpos[state] - 1])
  107. {
  108. int cl = make_state(to[state], link[state], fpos[state], mx_len[fpos[state] - 1]);
  109. link[state] = cl;
  110. }
  111. }
  112.  
  113. for(int state = 1; state < sz; state++) // sparse table, like in LCA
  114. up[state][0] = link[state];
  115. for(int lvl = 1; lvl < logn; lvl++)
  116. for(int state = 1; state < sz; state++)
  117. up[state][lvl] = up[up[state][lvl - 1]][lvl - 1];
  118.  
  119. vector<int> g[n + 1]; // this actually gives us reversed topsort
  120. for(int state = 1; state < sz; state++)
  121. g[len[state]].push_back(state);
  122. for(int ln = n; ln > 0; ln--)
  123. for(auto state: g[ln])
  124. {
  125. if(link[state])
  126. cnt[link[state]] += cnt[state];
  127. lpos[link[state]] = std::max(lpos[link[state]], lpos[state]);
  128. }
  129. }
  130.  
  131. int get(int pos, int ln) // kind of binary search on path to the root
  132. { // pos 1-based
  133. int state = st[pos - 1];
  134. for(int i = logn - 1; i >= 0; i--)
  135. if(len[up[state][i]] >= ln)
  136. state = up[state][i];
  137. return state;
  138. }
  139. } me[4 * maxn];
  140.  
  141. void build(int v = 1, int l = 1, int r = maxn)
  142. {
  143. if(r - l == 1)
  144. {
  145. s[l] = char(sigma) + s[l];
  146. me[v].build(s[l]);
  147. for(int state = 0; state < me[v].sz; state++)
  148. {
  149. me[v].ans[state] = l;
  150. me[v].max[state] = me[v].cnt[state];
  151. }
  152. return;
  153. }
  154. int m = (l + r) / 2;
  155. build(2 * v, l, m);
  156. build(2 * v + 1, m, r);
  157. me[v].build(me[2 * v].s + me[2 * v + 1].s);
  158. for(int state = 1; state < me[v].sz; state++)
  159. {
  160. if(me[v].fpos[state] <= (int) me[2 * v].s.size()) // we want to know states corresponding to strings from this state in children
  161. me[v].left[state] = me[2 * v].get(me[v].fpos[state], me[v].len[state]);
  162. if(me[v].lpos[state] > (int) me[2 * v].s.size())
  163. me[v].right[state] = me[2 * v + 1].get(me[v].lpos[state] - me[2 * v].s.size(), me[v].len[state]);
  164. me[v].max[state] = max(me[2 * v].max[me[v].left[state]], me[2 * v + 1].max[me[v].right[state]]);
  165. if(me[v].max[state] == me[2 * v].max[me[v].left[state]])
  166. me[v].ans[state] = me[2 * v].ans[me[v].left[state]];
  167. else
  168. me[v].ans[state] = me[2 * v + 1].ans[me[v].right[state]];
  169. }
  170. me[2 * v].clear(); // we don't need O(n log^2 n) memory
  171. me[2 * v + 1].clear();
  172. }
  173.  
  174. pair<int, int> get(int a, int b, int state, int v = 1, int l = 1, int r = maxn)
  175. {
  176. if(a <= l && r <= b)
  177. return {me[v].max[state], me[v].ans[state]};
  178. if(r <= a || b <= l)
  179. return {0, 0};
  180. int m = (l + r) / 2;
  181. auto A = get(a, b, me[v].left[state], 2 * v, l, m);
  182. auto B = get(a, b, me[v].right[state], 2 * v + 1, m, r);
  183. if(A.first >= B.first)
  184. return A;
  185. else
  186. return B;
  187. }
  188.  
  189. int main()
  190. {
  191. ios::sync_with_stdio(0);
  192. cin.tie(0);
  193. string Q;
  194. cin >> Q;
  195.  
  196. int n;
  197. cin >> n;
  198. for(int i = 0; i < n; i++)
  199. {
  200. cin >> s[i + 1];
  201. for(auto &it: s[i + 1])
  202. it -= 'a';
  203. }
  204. build(); // yeah, this thing builds!
  205. int state = 0, ln = 0;
  206. vector<int> states, lens;
  207. for(auto c: Q)
  208. {
  209. c -= 'a';
  210. while(state && !me[1].to[state][c])
  211. {
  212. state = me[1].link[state];
  213. ln = me[1].len[state];
  214. }
  215. if(me[1].to[state][c])
  216. {
  217. state = me[1].to[state][c];
  218. ln++;
  219. }
  220. lens.push_back(ln);
  221. states.push_back(state);
  222. }
  223.  
  224. int m;
  225. cin >> m;
  226. while(m--)
  227. {
  228. int l, r, pl, pr;
  229. cin >> l >> r >> pl >> pr;
  230. if(pr - pl + 1 > lens[pr - 1])
  231. {
  232. cout << l << ' ' << 0 << "\n";
  233. continue;
  234. }
  235. int state = me[1].get(me[1].fpos[states[pr - 1]], pr - pl + 1);
  236. auto ans = get(l, r + 1, state);
  237. cout << max(l, ans.second) << ' ' << ans.first << "\n";
  238. }
  239. return 0;
  240. }
  241.  
Runtime error #stdin #stdout 1.6s 280512KB
stdin
Standard input is empty
stdout
Standard output is empty