tandem/TandemRepeat_artur.java

  1 import java.io.BufferedReader;
  2 import java.io.InputStreamReader;
  3 
  4 public class TandemRepeat_artur {
  5 
  6   static final int MAXN = 100100;
  7   static final int[] p1 = new int[MAXN];
  8   static final int[] p2 = new int[MAXN];
  9   static final int[] p3 = new int[MAXN];
 10   static final int[] p4 = new int[MAXN];
 11 
 12   static char[] a;
 13   static long count;
 14 
 15   public static void main(String[] args) throws Exception {
 16     BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 17 
 18     while (true) {
 19       String s = in.readLine();
 20       if ("0".equals(s))
 21         break;
 22 
 23       a = s.toCharArray();
 24       count = 0;
 25       count(0, a.length);
 26       System.out.println(count);
 27     }
 28   }
 29 
 30   static void count(int l, int r) {
 31     int n = r - l;
 32     if (n <= 1)
 33       return;
 34 
 35     int x = n / 2, y = n - x, m = l + x;
 36 
 37     count(l, m);
 38     count(m, r);
 39 
 40     reverse(l, m);
 41     prefixes(l, m, p1);
 42     reverse(m, r);
 43     reverse(l, r);
 44     prefixes(l, r, p2);
 45     reverse(l, r);
 46     prefixes(l, r, p3);
 47     reverse(m, r);
 48     reverse(l, m);
 49     prefixes(m, r, p4);
 50 
 51     int len, i, j, temp = n - 1 + x;
 52     for (int k = 0; k < n; k++) {
 53       if (k < x) {
 54         len = x - k;
 55         i = len < x ? p1[len] : 0;
 56         j = y + k < n ? p2[y + k] : 0;
 57       } else {
 58         len = k - x + 1;
 59         i = temp - k < n ? p3[temp - k] : 0;
 60         j = len < y ? p4[len] : 0;
 61       }
 62 
 63       if (x < i)
 64         i = x;
 65       if (y < j)
 66         j = y;
 67       if (i + j >= len) {
 68         i = Math.min(i, k < x ? len - 1 : len);
 69         j = Math.max(len - j, 1);
 70         if (i > 0 && j <= i)
 71           count += i - j + 1;
 72       }
 73     }
 74   }
 75 
 76   static void prefixes(int l, int r, int[] p) {
 77     int n = r - l;
 78     for (int k = 1, i = 0, j = 0; k < n; k++)
 79       if (p[k - i] + k <= j)
 80         p[k] = p[k - i];
 81       else {
 82         i = k;
 83         if (k > j)
 84           j = k;
 85         for (p[k] = j - k; j < n && a[j + l] == a[p[k] + l]; j++, p[k]++)
 86           ;
 87         j--;
 88       }
 89   }
 90 
 91   static void reverse(int l, int r) {
 92     for (int i = l, j = r - 1; i < j; i++, j--) {
 93       char t = a[i];
 94       a[i] = a[j];
 95       a[j] = t;
 96     }
 97   }
 98 }