题目
如果一个字符串可以被拆分为 \text{AABB}AABB 的形式，其中 \text{A}A 和 \text{B}B 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。 例如，对于字符串 \texttt{aabaabaa} aabaabaa ，如果令 \text{A}=\texttt{aab}A=aab，\text{B}=\texttt{a}B=a，我们就找到了这个字符串拆分成 \text{AABB}AABB 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。 比如我们令 \text{A}=\texttt{a}A=a，\text{B}=\texttt{baa}B=baa，也可以用 \text{AABB}AABB 表示出上述字符串；但是，字符串 \texttt{abaabaa}abaabaa 就没有优秀的拆分。
现在给出一个长度为 nn 的字符串 SS，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。 在一个拆分中，允许出现 \text{A}=\text{B}A=B。例如 \texttt{cccc}cccc 存在拆分 \text{A}=\text{B}=\texttt{c}A=B=c。 字符串本身也是它的一个子串。
思路
hash有95分，然后剩下5分要费很大劲 显然 AABB 是由两个 AA 串拼起来的 考虑令
f
(
i
)
f(i)
f(i) 表示以
i
i
i 结尾的
A
A
\rm{AA}
AA 数量，
g
(
i
)
g(i)
g(i) 表示以
i
i
i 开头的
A
A
\rm{AA}
AA 数量，答案就是
∑
f
(
i
)
g
(
i
+
1
)
\sum f(i)g(i+1)
∑f(i)g(i+1) 枚举
A
\rm{A}
A 的长度
L
L
L ，每隔
L
L
L 就设置一个关键点，对于长度等于
L
L
L 的
A
\rm{A}
A ，
A
A
\rm{AA}
AA 一定经过相邻的恰好两个关键点 画图可以发现，对于两个相邻的关键点
x
,
y
x,y
x,y，如果
A
A
\rm{AA}
AA 经过了其，那么一定满足
l
c
s
(
x
,
y
)
+
l
c
p
(
x
,
y
)
≥
L
lcs(x,y)+lcp(x,y)\geq L
lcs(x,y)+lcp(x,y)≥L ，这里
l
c
s
(
x
,
y
)
lcs(x,y)
lcs(x,y) 指
S
t
r
(
1
,
x
)
Str(1,x)
Str(1,x) 和
S
t
r
(
1
,
y
)
Str(1,y)
Str(1,y) 的最长公共后缀长度，这里
l
c
p
(
x
,
y
)
lcp(x,y)
lcp(x,y) 指
S
t
r
(
x
,
n
)
Str(x,n)
Str(x,n) 和
S
t
r
(
y
,
n
)
Str(y,n)
Str(y,n) 的最长公共前缀的长度 这样的话建两个
s
a
sa
sa 分别存原串和原串的反串即可 因为
l
c
s
(
x
,
y
)
+
l
c
p
(
x
,
y
)
lcs(x,y)+lcp(x,y)
lcs(x,y)+lcp(x,y) 可能大于
L
L
L ，所以对
f
,
g
f,g
f,g 的贡献其实是一段区间，差分实现区间加就好 对于每个
L
L
L ，关键点的下标是
x
L
xL
xL ，关键点的个数是
L
L
L 在
[
1
,
n
]
[1,n]
[1,n] 内的倍数个数，处理
l
c
s
,
l
c
p
lcs,lcp
lcs,lcp 用
s
t
st
st 表，询问复杂度是
O
(
1
)
O(1)
O(1) ，因此这一部分时间复杂度是
O
(
n
log
n
)
O(n\log n)
O(nlogn)
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
const int inf
=0x3f3f3f3f;
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int N
=3e4;
int n
,f
[N
+7],g
[N
+7];
struct SuffixArray
{
char s
[N
+7];
int m
,c
[N
+7],tp
[N
+7],rk
[N
+7],sa
[N
+7];
int h
[N
+7],st
[N
+7][20];
void csort(){
for(int i
=0;i
<=m
;i
++) c
[i
]=0;
for(int i
=1;i
<=n
;i
++) c
[rk
[i
]]++;
for(int i
=1;i
<=m
;i
++) c
[i
]+=c
[i
-1];
for(int i
=n
;i
>=1;i
--) sa
[c
[rk
[tp
[i
]]]--]=tp
[i
];
}
void build(){
memset(c
,0,sizeof c
);
memset(tp
,0,sizeof tp
);
memset(rk
,0,sizeof rk
);
memset(sa
,0,sizeof sa
);
memset(h
,0,sizeof h
);
memset(st
,0,sizeof st
);
for(int i
=1;i
<=n
;i
++) rk
[i
]=s
[i
],tp
[i
]=i
;
m
=128,csort();
for(int w
=1,p
=1,i
;p
<n
;w
<<=1,m
=p
){
for(p
=0,i
=n
-w
+1;i
<=n
;i
++) tp
[++p
]=i
;
for(i
=1;i
<=n
;i
++)if(sa
[i
]>w
) tp
[++p
]=sa
[i
]-w
;
csort(),swap(rk
,tp
),rk
[sa
[1]]=p
=1;
for(i
=2;i
<=n
;rk
[sa
[i
]]=p
,i
++)
if(tp
[sa
[i
]]!=tp
[sa
[i
-1]]||tp
[sa
[i
]+w
]!=tp
[sa
[i
-1]+w
]) p
++;
}
for(int i
=1,j
,k
=0;i
<=n
;h
[rk
[i
++]]=k
)
for(k
=k
?k
-1:k
,j
=sa
[rk
[i
]-1];s
[i
+k
]==s
[j
+k
];k
++);
for(int i
=1;i
<=n
;i
++) st
[i
][0]=h
[i
];
for(int w
=1;w
<=18;w
++)
for(int i
=1;i
+(1<<w
)-1<=n
;i
++)
st
[i
][w
]=min(st
[i
][w
-1],st
[i
+(1<<(w
-1))][w
-1]);
}
int Lcp(int a
,int b
){
int l
=rk
[a
],r
=rk
[b
];
if(l
>r
) swap(l
,r
); l
++;
int k
=log2(r
-l
+1);
return min(st
[l
][k
],st
[r
-(1<<k
)+1][k
]);
}
}a
,b
;
void KonnyWen(){
memset(f
,0,sizeof f
);
memset(g
,0,sizeof g
);
scanf("%s",&a
.s
[1]),n
=strlen(&a
.s
[1]);
for(int i
=1;i
<=n
;i
++) b
.s
[i
]=a
.s
[n
+1-i
];
a
.build(),b
.build();
for(int i
=1;i
<=n
;i
++) f
[i
]=g
[i
]=0;
for(int w
=1;w
<=(n
>>1);w
++)
for(int i
=w
;i
<=n
;i
+=w
){
int l
=i
,r
=i
+w
;
int lcp
=min(w
,a
.Lcp(l
,r
));
int lcs
=min(w
-1,b
.Lcp(n
-(l
-1)+1,n
-(r
-1)+1));
if(lcp
+lcs
>=w
){
int cov
=lcp
+lcs
-w
+1;
f
[r
+lcp
-cov
]++,f
[r
+lcp
]--;
g
[l
-lcs
]++,g
[l
-lcs
+cov
]--;
}
}
for(int i
=1;i
<=n
;i
++) f
[i
]+=f
[i
-1],g
[i
]+=g
[i
-1];
ll ans
=0;
for(int i
=1;i
<n
;i
++) ans
+=f
[i
]*g
[i
+1];
printf("%lld\n",ans
);
}
int main(){
int t
; scanf("%d",&t
);
while(t
--) KonnyWen();
return 0;
}
