fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/oag72o
language:
Java (12.0.1)
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!