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
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int T, f[30005], g[30005], mlg[30005];
ll ans;
struct SuffixArray{
int n, tmp[30005], rnk[30005], saa[30005], m, p, cnt[30005], st[30005][15], hei[30005];
char ss[30005];
void init(){
m = 128;
p = 0;
memset(tmp, 0, sizeof(tmp));
memset(rnk, 0, sizeof(rnk));
memset(saa, 0, sizeof(saa));
memset(hei, 0, sizeof(hei));
memset(cnt, 0, sizeof(cnt));
memset(st, 0, sizeof(st));
}
void sasort(){
for(int i=0; i<m; i++) cnt[i] = 0;
for(int i=0; i<n; i++) cnt[rnk[i]]++;
for(int i=1; i<m; i++) cnt[i] += cnt[i-1];
for(int i=n-1; i>=0; i--) saa[--cnt[rnk[tmp[i]]]] = tmp[i];
}
void getLcp(){
int h=0;
for(int i=1; i<=n; i++) rnk[saa[i]] = i;
for(int i=0; i<n; i++){
if(h) h--;
int j=saa[rnk[i]-1];
while(ss[i+h]==ss[j+h]) h++;
hei[rnk[i]] = h;
}
for(int i=1; i<=n; i++) st[i][0] = hei[i];
for(int i=1; i<=14; i++)
for(int j=1; j<=n && j+(1<<(i-1))<=n; j++)
st[j][i] = min(st[j][i-1], st[j+(1<<(i-1))][i-1]);
}
void buildSA(){
ss[n] = 0; n++;
for(int i=0; i<n; i++){
rnk[i] = ss[i];
tmp[i] = i;
}
sasort();
for(int j=1; p<n; j<<=1){
p = 0;
for(int i=n-j; i<n; i++) tmp[p++] = i;
for(int i=0; i<n; i++)
if(saa[i]>=j)
tmp[p++] = saa[i] - j;
sasort();
swap(rnk, tmp);
p = 1;
rnk[saa[0]] = 0;
for(int i=1; i<n; i++)
if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])
rnk[saa[i]] = p - 1;
else
rnk[saa[i]] = p++;
m = p;
}
n--;
getLcp();
}
int lcp(int x, int y){
int l=min(rnk[x], rnk[y])+1, r=max(rnk[x], rnk[y]);
return min(st[l][mlg[r-l+1]], st[r-(1<<mlg[r-l+1])+1][mlg[r-l+1]]);
}
}A, B;
int main(){
cin>>T;
for(int i=2; i<=30000; i++)
mlg[i] = mlg[i>>1] + 1;
while(T--){
A.init(); B.init();
scanf("%s", A.ss);
A.n = B.n = strlen(A.ss);
for(int i=0; i<A.n; i++)
B.ss[A.n-1-i] = A.ss[i];
A.buildSA(); B.buildSA();
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
ans = 0;
for(int len=1; 2*len<=A.n; len++){
int j=len*2-1;
for(int i=len-1; j<A.n; ){
int x=min(A.lcp(i, j), len);
int y=min(B.lcp(A.n-i, A.n-j), len-1);
int t=x+y-len+1;
if(x+y>=len){
g[i-y]++; g[i-y+t]--;
f[j+x-t]++; f[j+x]--;
}
i += len;
j += len;
}
}
for(int i=1; i<A.n; i++){
f[i] += f[i-1];
g[i] += g[i-1];
}
for(int i=1; i<A.n-1; i++)
ans += (ll)f[i] * g[i+1];
printf("%lld\n", ans);
}
return 0;
}
|