NOI2016 优秀的拆分（二分+哈希+差分数组）

发表于 |
字数统计: 1,400字 | 阅读时长 ≈ 7min

【NOI2016】优秀的拆分

问题描述

如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

  1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
  2. 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
  3. 字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 $T$，表示数据的组数。
接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

输出格式

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

样例输入

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

样例输出

3
5
4
7

提示

对于全部的测试点，$1 \leq T \leq 10, \ n \leq 30000$。

考虑枚举$AA$与$BB$的分界，令$A[i]$表示以$i$结尾的形如$AA$的串的个数，$B[i]$表示以$i$开头的形如$BB$的串的个数，那么$Ans=\sum A[i]\times B[i+1]$

那么考虑如何求出$A[i]$和$B[i]$，下面只讨论$A[i]$，$B[i]$同理。

考虑一个长为$2L$的形如$AA$的串，那么该串一定经过形如了$s[iL]$和$s[(i+1)L]$两个位置，我们考虑先枚举$L$，再枚举$pos=iL$，那么算出$s[iL],s[(i+1)L]$往前后分别能匹配多长，假设往前能匹配的长度位$pre（包含iL）$，往后能匹配的长度为$suf（包含iL）$，那么可以发现在区间$[(i+1)L-pre+L,(i+1)L+suf-1]$都可以作为一个$AA$串的结尾。因此只需要区间$+1$即可。这里可以用差分数组来做。

但是注意到直接这样算会出现重复，因此最后的区间左端点应该是$max{(i+1)L-pre+L,(i+1)L}$，区间右端点应该是$min{(i+1)L+suf-1,(i+2)L-1}$

最后，处理往前和往后的匹配长度时，可以用后缀自动机或后缀数组处理，也可以直接用哈希+二分解决，复杂度都差不多。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 30005
#define ll long long
#define ull unsigned long long
using namespace std;
char buf[1<<20],*p11,*p22;
#define GC (p11==p22&&(p22=(p11=buf)+fread(buf,1,1000000,stdin),p11==p22)?0:*p11++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
inline int _S(char *c)
{
	char *t=c,ch=GC;
	while(ch<'a'||ch>'z')ch=GC;
	for(;ch>='a'&&ch<='z';ch=GC)*t++=ch;
	*t=0;return t-c;
}
const ull p1=1234321237;
const ull p2=1313131312;
ull Aash[N],Bash[N],Pow1[N],Pow2[N];
long long ans;
int T,n,A[N],B[N];
char s[N];
void Init()
{
	fill(Aash,Aash+n+2,0);
	fill(Bash,Bash+n+2,0);
	fill(A,A+n+2,0);
	fill(B,B+n+2,0);
}
bool check(int x1,int y1,int x2,int y2)
{
	ull x=Aash[y1]-Aash[x1-1]*Pow1[y1-x1+1];
	ull y=Aash[y2]-Aash[x2-1]*Pow1[y2-x2+1];
	ull p=Bash[y1]-Bash[x1-1]*Pow2[y1-x1+1];
	ull q=Bash[y2]-Bash[x2-1]*Pow2[y2-x2+1];
	return x==y&&p==q;
}
int Gpre(int x,int y,int L)
{
	int l=1,r=min(x,L),mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(x-mid+1,x,y-mid+1,y))l=mid+1;
		else r=mid-1;
	}
	return r;
}
int Gsuf(int x,int y,int L)
{
	int l=1,r=min(n-y+1,L),mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(x,x+mid-1,y,y+mid-1))l=mid+1;
		else r=mid-1;
	}
	return r;
}
void Get(int x,int y,int L)
{
	int i,j,k,pre,suf,l,r;
	pre=Gpre(x,y,L);
	suf=Gsuf(x,y,L);
	l=max(y-pre+L,y);
	r=min(y+suf-1,y+L-1);
	if(l<=r)
	{
		A[l]++;A[r+1]--;
		B[l-(L<<1)+1]++;
		B[r-(L<<1)+2]--;
	}
}
int main()
{
	int i,j,k,x,y;
	_R(T);Pow1[0]=Pow2[0]=1;
	while(T--)
	{
		n=_S(s+1);Init();ans=0;
		for(i=1;i<=n;i++)Pow1[i]=Pow1[i-1]*p1;
		for(i=1;i<=n;i++)Pow2[i]=Pow2[i-1]*p2;
		for(i=1;i<=n;i++)Aash[i]=Aash[i-1]*p1+s[i];
		for(i=1;i<=n;i++)Bash[i]=Bash[i-1]*p2+s[i];
		for(i=1;i<=(n>>1);i++)
		for(j=1;j+i<=n;j+=i)if(s[j]==s[j+i])Get(j,j+i,i);
		for(i=1;i<=n;i++)A[i]+=A[i-1],B[i]+=B[i-1];
		for(i=1;i<n;i++)ans+=1ll*A[i]*B[i+1];
		printf("%lld\n",ans);
	}
}