bzoj 4962 简单的字符串

Posted on | Edited on | Views:

$Manacher$ .

  • 不知道性质的话应该挺难做的…
  • 先枚举子串中心,往两侧拓展,将走到的位置的字符交替写下来,记作 $S$ .
  • 比如字符串是 $abcdacce$ ,以 $d$ 右侧的那个位置为中心,则 $S=daccbcae$ (此处先写左边).
  • 若中心的两侧长度为 $L$ 的两个子串循环同构,则 $S$ 中对应的长度为 $2L$ 的前缀能被 $1$ 或 $2$ 个偶回文串拼接成.
  • 证明:如果左右两个子串完全相同,那么这个长度为 $2L$ 的前缀自身就是一个偶回文串.否则,若左右两个子串不同,但循环同构,那么设右边的串为 $s_1,s_2,\dots s_L$ ,左边的串为 $s_i,s_{i+1},\dots,s_L,s_1,s_2\dots,s_{i-1}$ .
  • 那么这个长度为 $2L$ 的前缀就应该是 $(s_{i-1},s_1,s_{i-2},s_2,\dots,s_1,s_{i-1})+(s_L,s_i,s_{L-1},s_{i+1},\dots,s_i,s_L)$ . 显然加号两边的串都是偶回文串.
  • 还有一个性质,若 $S=u+v$ , $u$ 和 $v$ 都是偶回文串,那么要么 $u$ 是 $S$ 的最长偶回文前缀,要么 $v$ 是 $S$ 的最长偶回文后缀.Claris的证明
  • 于是用 $Manacher$ 跑出每个位置的最长回文半径 $rmax$ ,对于每个前缀判断一下拆成 最长偶回文前缀 + 偶回文串 与拆成 偶回文串 + 最长偶回文后缀 是否有一个合法即可.
  • 时间复杂度 $O(n^2)$ . 若用 $Hash$ 代替 $Manacher$ 则为 $O(n^2 logn)$ .
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e3+10;
int ch[MAXN],s[MAXN];
int n,rmax[MAXN],pre[MAXN];
int solve(int p)
{
	int len=0;
	for(int i=p,j=p+1;i>=1 && j<=n;--i,++j)
		s[++len]=ch[i],s[++len]=ch[j];
	fill(pre+1,pre+2+len,0);
	int r=0,pos=1;
	for(int i=1;i<=len;++i)
	{
		int mx=min(max(r-i,0),rmax[2*pos-i]);
		while(i+mx+1<=n && i-mx>0 && s[i+mx+1]==s[i-mx])
			++mx;
		rmax[i]=mx;
		if(i+mx>=r)
			r=i+mx,pos=i;
		pre[i+rmax[i]]=max(pre[i+rmax[i]],rmax[i]);
	}
	for(int i=len;i>=1;--i)
		pre[i]=max(pre[i],pre[i+1]-1);
	for(int i=len;i>=1;i-=2)
		pre[i]<<=1;
	int mx=0,res=0;
	for(int i=2;i<=len;i+=2)
	{
		if(rmax[i/2]==i/2)
			mx=i;
		if(rmax[(i+mx)/2]>=(i-mx)/2 || rmax[(i-pre[i])/2]>=(i-pre[i])/2)
			++res;
	}
	return res;
}
int main()
{
	int ans=0;
	n=read();
	for(int i=1;i<=n;++i)
		ch[i]=read();
	for(int i=1;i<n;++i)
		ans+=solve(i);
	cout<<ans<<endl;
	return 0;
}