fork download
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.Locale;
  4. import java.util.StringTokenizer;
  5.  
  6. public class TaskE {
  7. private final InputReader reader;
  8. private final OutputWriter writer;
  9.  
  10. public TaskE(InputReader reader, OutputWriter writer) {
  11. this.reader = reader;
  12. this.writer = writer;
  13. }
  14.  
  15. public static void main(String[] args) {
  16. InputReader reader = new InputReader(System.in);
  17. OutputWriter writer = new OutputWriter(System.out);
  18. new TaskE(reader, writer).run();
  19. writer.writer.flush();
  20. }
  21.  
  22. int[] L;
  23. int[][] LT;
  24. int[] deg2;
  25.  
  26. int lcp(int a, int b) {
  27. if (a > b) {
  28. int t = a;
  29. a = b;
  30. b = t;
  31. }
  32. if (a == b)
  33. throw new AssertionError();
  34. int k = deg2[b - a];
  35. return Math.min(LT[k][a], LT[k][b - (1 << k)]);
  36. }
  37.  
  38. void buildSuffixArray(char[] S) {
  39. int n = S.length;
  40. int[] P, nP, eq, neq, cnt;
  41. P = new int[n];
  42. nP = new int[n];
  43. cnt = new int[Math.max(28, n)];
  44. eq = new int[n];
  45. neq = new int[n];
  46. for (int i = 0; i < n; i++)
  47. cnt[S[i] - 'a']++;
  48. for (int i = 1; i < 28; i++)
  49. cnt[i] += cnt[i - 1];
  50. for (int i = n - 1; i >= 0; i--) {
  51. P[--cnt[S[i] - 'a']] = i;
  52. eq[i] = S[i] - 'a';
  53. }
  54. int mx = 28;
  55. for (int k = 1; k < n && (k == 1 || mx != n); k <<= 1) {
  56. for (int i = 0; i < n; i++)
  57. P[i] = (P[i] >= k) ? P[i] - k : P[i] - k + n;
  58. Arrays.fill(cnt, 0);
  59. for (int i = 0; i < n; i++)
  60. cnt[eq[P[i]]]++;
  61. for (int i = 1; i < mx; i++)
  62. cnt[i] += cnt[i - 1];
  63. for (int i = n - 1; i >= 0; i--)
  64. nP[--cnt[eq[P[i]]]] = P[i];
  65. neq[nP[0]] = 0;
  66. for (int i = 1; i < n; i++)
  67. neq[nP[i]] = neq[nP[i - 1]] + ((eq[nP[i]] != eq[nP[i - 1]] ||
  68. eq[(nP[i] + k < n) ? nP[i] + k : nP[i] + k - n] !=
  69. eq[(nP[i - 1] + k < n) ? nP[i - 1] + k : nP[i - 1] + k - n]) ? 1 : 0);
  70. mx = neq[nP[n - 1]] + 1;
  71. for (int i = 0; i < n; i++) {
  72. P[i] = nP[i];
  73. eq[i] = neq[i];
  74. }
  75. }
  76. L = new int[n];
  77. int[] IP = new int[n];
  78. for (int i = 0; i < n; i++)
  79. IP[P[i]] = i;
  80. int cur = 0;
  81. for (int i = 0; i < n; i++) {
  82. if (IP[i] + 1 != n) {
  83. int a = i, b = P[IP[i] + 1];
  84. while (S[a + cur] == S[b + cur])
  85. cur++;
  86. L[IP[a]] = cur;
  87. }
  88. cur = Math.max(cur - 1, 0);
  89. }
  90. deg2 = new int[n + 1];
  91. deg2[0] = -42;
  92. deg2[1] = 0;
  93. for (int i = 2; i <= n; i++)
  94. deg2[i] = 1 + deg2[i >> 1];
  95. LT = new int[deg2[n] + 1][n];
  96. for (int i = 0; i < n; i++)
  97. LT[0][i] = L[i];
  98. for (int l = 1; l <= deg2[n]; l++)
  99. for (int i = 0; i + (1 << l) <= n; i++)
  100. LT[l][i] = Math.min(LT[l - 1][i], LT[l - 1][i + (1 << (l - 1))]);
  101. SA = P;
  102. ISA = IP;
  103. }
  104.  
  105. class Event implements Comparable<Event> {
  106. int t;
  107. int id;
  108. int a, b;
  109. Event(int t, int id, int a, int b) {
  110. this.t = t;
  111. this.a = a;
  112. this.b = b;
  113. this.id = id;
  114. }
  115. @Override
  116. public int compareTo(Event other) {
  117. return Integer.compare(this.t, other.t);
  118. }
  119. }
  120.  
  121. int[] SA, ISA;
  122. int[] beg;
  123. int[] len;
  124. int[] color;
  125. Event[] E;
  126. int ept = 0;
  127.  
  128. void addQuery(int a, int b, int k, int id) {
  129. int ln = len[k];
  130. k = ISA[beg[k]];
  131. int l = -1, r = k;
  132. while (r - l > 1) {
  133. int m = (l + r) / 2;
  134. if (lcp(m, k) < ln)
  135. l = m;
  136. else
  137. r = m;
  138. }
  139. int L = r;
  140. l = k;
  141. r = SA.length;
  142. while (r - l > 1) {
  143. int m = (l + r) / 2;
  144. if (lcp(k, m) < ln)
  145. r = m;
  146. else
  147. l = m;
  148. }
  149. int R = l;
  150. E[ept++] = new Event(L - 1, ~id, a, b);
  151. E[ept++] = new Event(R, id, a, b);
  152. }
  153.  
  154. int[] F;
  155. void inc(int x) {
  156. for(; x < F.length; x |= x + 1)
  157. F[x]++;
  158. }
  159.  
  160. int get(int x) {
  161. int ans = 0;
  162. for (; x >= 0; x &= x + 1, --x)
  163. ans += F[x];
  164. return ans;
  165. }
  166.  
  167. public void run() {
  168. int n = reader.nextInt();
  169. int q = reader.nextInt();
  170. char[] S = new char[1000 * 1000 + 42];
  171. beg = new int[n];
  172. len = new int[n];
  173. int pt = 0;
  174. for (int i = 0; i < n; i++) {
  175. char[] T = reader.next().toCharArray();
  176. len[i] = T.length;
  177. beg[i] = pt;
  178. for (int j = 0; j < T.length; j++) {
  179. S[pt + j] = T[j];
  180. }
  181. pt += T.length;
  182. S[pt++] = 'z' + 1;
  183. }
  184. S[pt++] = 'z' + 2;
  185. S = Arrays.copyOf(S, pt);
  186. color = new int[pt];
  187. pt = 0;
  188. for (int i = 0; i < n; i++) {
  189. for (int j = 0; j < len[i]; j++)
  190. color[pt + j] = i;
  191. pt += len[i] + 1;
  192. }
  193.  
  194. buildSuffixArray(S);
  195. /*for (int i = 0; i < pt; i++)
  196.   writer.printf("%2d %2d %s\n", SA[i], L[i], String.valueOf(S, SA[i], pt - SA[i]));
  197.   writer.printf("\n");
  198.   writer.writer.flush();*/
  199.  
  200.  
  201. E = new Event[2 * q];
  202. for (int i = 0; i < q; i++) {
  203. int l = reader.nextInt() - 1;
  204. int r = reader.nextInt() - 1;
  205. int k = reader.nextInt() - 1;
  206. addQuery(l, r, k, i);
  207. }
  208. Arrays.sort(E);
  209. F = new int[n];
  210. int[] ans = new int[q];
  211. int cpt = 0;
  212. for (Event e : E) {
  213. while (cpt <= e.t) {
  214. inc(color[SA[cpt]]);
  215. cpt++;
  216. }
  217. int id = e.id;
  218. int mul = (id >= 0) ? 1 : -1;
  219. id = (id >= 0) ? id : ~id;
  220. int a = e.a;
  221. int b = e.b;
  222. ans[id] += mul * (get(b) - get(a - 1));
  223. }
  224. for (int a : ans)
  225. writer.printf("%d\n", a);
  226. }
  227.  
  228.  
  229. static class InputReader {
  230. public BufferedReader reader;
  231. public StringTokenizer tokenizer;
  232.  
  233. public InputReader(InputStream stream) {
  234. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  235. tokenizer = null;
  236. }
  237.  
  238. public String next() {
  239. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  240. try {
  241. tokenizer = new StringTokenizer(reader.readLine());
  242. } catch (IOException e) {
  243. throw new RuntimeException(e);
  244. }
  245. }
  246. return tokenizer.nextToken();
  247. }
  248.  
  249. public int nextInt() {
  250. return Integer.parseInt(next());
  251. }
  252.  
  253. public double nextDouble() {
  254. return Double.parseDouble(next());
  255. }
  256.  
  257. public long nextLong() {
  258. return Long.parseLong(next());
  259. }
  260. }
  261.  
  262. static class OutputWriter {
  263. public PrintWriter writer;
  264.  
  265. OutputWriter(OutputStream stream) {
  266. writer = new PrintWriter(stream);
  267. }
  268.  
  269. public void printf(String format, Object... args) {
  270. writer.print(String.format(Locale.ENGLISH, format, args));
  271. }
  272. }
  273. }
  274.  
  275.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:6: error: class TaskE is public, should be declared in a file named TaskE.java
public class TaskE {
       ^
1 error
stdout
Standard output is empty