Suffix Array.

Description

Define a division of a string is good, if it forms like $AABB$, where the four substrings a linked one after another, and both of them are non-empty.

Given a string $S$ with length $N$, calculate how many good divisions there are of all divisions of all substrings of $S$. Notice that two substrings with the same contents but appear at different positions are regarded as different.

Solution

On site of NOI2016, just use hash and binary_search two calculate LCP can get 95 of 100 points:)

The last test case with $N \le 30000$ needs an $O(n \ln n)$ algorithm.

Try to reconstruct the model of this problem. We can get ans by $\sum_{i} forward \times backward$. And how to quickly calculate them?

Enumerate all possible length $L$ of $A$ and $B$ (in description), and choose $\frac{N}{L}$ key points on $S$.

We have such a conclusion: a substring like $AA$ with each having a length of $L$ will exactly cover two key points.

So by calculating the common prefix / suffix before / after a pair of key points, we can get the contribution of every substring to the ans.

Build a difference array of ans, and every time we get an interval of possible $AA$, put $+1$ at first and $-1$ after last. Don’t forget put tag in a reversing way to calculate backward answers.

Then get prefix sum / suffix sum of the array to get $forward$ and $backward$. Multiply each pair of adjacent points’ numbers together.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#pragma GCC diagnostic ignored "-Wchar-subscripts"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 30005;

int n, lo2[maxn];
ll bg[maxn], ed[maxn], S[maxn], T[maxn];
char str[maxn];

struct SuffixArray
{
  char s[maxn];
  int sa[maxn], bkt1[maxn], bkt2[maxn], rk[maxn], ht[maxn];
  int fir[maxn], sec[maxn], tmp[maxn];
  int rmq[maxn][16];
  void init() {
    memset(sa, 0, sizeof sa);
    memset(rk, 0, sizeof rk);
    memset(ht, 0, sizeof ht);
    memset(bkt1, 0, sizeof bkt1); 
    memset(bkt2, 0, sizeof bkt2);
    memset(rmq, 0, sizeof rmq);
    memset(fir, 0, sizeof fir);
    memset(sec, 0, sizeof sec);
    memset(s, 0, sizeof s);
    memset(tmp, 0, sizeof tmp);
  }
  void build() {
    for (int i = 1; i <= n; ++i) bkt1[s[i]]++;
    for (int i = 1; i < 128; ++i) bkt1[i] += bkt1[i - 1];//, printf("%d\n", bkt1[i]);
    //puts("---");
    for (int i = n; i; --i)
      sa[bkt1[s[i]]--] = i;
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
    for (int len = 1; rk[sa[n]] < n; len <<= 1) {
      memset(bkt1, 0, sizeof bkt1);
      memset(bkt2, 0, sizeof bkt2);
      for (int i = 1; i <= n; ++i) {
        fir[i] = rk[i];
        bkt1[fir[i]]++;
        sec[i] = (i + len <= n ? rk[i + len] : 0);
        bkt2[sec[i]]++;
      }
      for (int i = 1; i <= n; ++i)
        bkt1[i] += bkt1[i - 1], bkt2[i] += bkt2[i - 1];
      for (int i = n; i; --i)
        tmp[bkt2[sec[i]]--] = i;
      for (int i = n; i; --i)
        sa[bkt1[fir[tmp[i]]]--] = tmp[i];
      rk[sa[1]] = 1;
      for (int i = 2; i <= n; ++i)
        rk[sa[i]] = rk[sa[i - 1]] + (fir[sa[i]] != fir[sa[i - 1]] || sec[sa[i]] != sec[sa[i - 1]]);
    }

    for (int i = 1, j = 0; i <= n; ++i) {
      j = j ? j - 1 : 0;
      while (s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
      ht[rk[i]] = j;
      //printf("%d\n", ht[rk[i]] );
    }

    for (int i = 1; i <= n; ++i) 
      rmq[i][0] = ht[i];//, printf("%d\n", ht[i]);
    for (int i = 1; (1 << i) <= n; ++i)
      for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
        rmq[j][i] = min(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
      }
  }
  inline int query(int l, int r) {
    int len = r - l + 1; 
    return min(rmq[l][lo2[len]], rmq[r - (1 << lo2[len]) + 1][lo2[len]]);
  }
}SA, SA2;

int main() {
  int Ts; scanf("%d", &Ts);
  lo2[1] = 0;
  for (int i = 2; i <= 30000; ++i)
    lo2[i] = lo2[i >> 1] + 1;
  while (Ts--) {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    SA.init();
    SA2.init();
    for (int i = 1; i <= n; ++i) 
      SA.s[i] = str[i], SA2.s[i] = str[n - i + 1];
    
    SA.build();
    SA2.build();
    memset(bg, 0, sizeof bg);
    memset(ed, 0, sizeof ed);
    memset(S, 0, sizeof S);
    memset(T, 0, sizeof T);
    for (int i = 1; i <= n; ++i) {
      for (int p = i + 1; p <= n; p += i) {
        int lst = SA.rk[p - i + 1], ths = SA.rk[p + 1]; //forward two position
        if (lst > ths) swap(lst, ths);
        int rlst = SA2.rk[n - (p - i) + 1], rths = SA2.rk[n - p + 1]; //backward two posisiton
        if (rlst > rths) swap(rlst, rths);
        int lcp = SA.query(lst + 1, ths);
        int rlcp = SA2.query(rlst + 1, rths); 
        //RMQ -> LCP, +1 because height means LCP(rk[i], rk[i - 1])
        if (lcp + rlcp < i || !rlcp) continue;
        int l = max(p - 2 * i + 1, p - i - rlcp + 1);
        int r = min(p + i - 1, p + lcp);
        S[l]++; S[r - 2 * i + 2]--; //forward possible interval
        T[l + 2 * i - 1]++; T[r + 1]--; //backward possible interval
      }
    }
    for (int i = 1; i <= n; ++i)
      bg[i] = bg[i - 1] + S[i], ed[i] = ed[i - 1] + T[i];
    ll ans = 0;
    for (int i = 2; i <= n; ++i)
      ans += bg[i] * ed[i - 1];
    printf("%lld\n", ans);
  }
  return 0;
}