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

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!