fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rpw2E8
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!