JSOI2016扭动的回文串

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

【JSOI2016】扭动的回文串

img

输入格式

第一行包含一个正整数 N。
第二行包含一个长度为 N 的由大写字母组成的字符串 A。
第三行包含一个长度为 N 的由大写字母组成的字符串 B。

输出格式

输出的第一行一个整数，表示最长的扭动回文串。

样例输入 1

5
ABCDE
BAECB

样例输出 1

5

样例输入 2

30
AABABAAAAABBBAAAAAABBAABAABABA
AAAAAAABABBAAAAAABABAAAABAAAAB

样例输出 2

23

提示

样例1解释
最佳方案中的扭动回文串如下所示（不在回文串中的字符用 . 表示）：

1
2
.BC..
..ECB

对于所有的数据，1≤N≤10^5

情况1,2就是裸的Manacher，跑完之后分别得到两个字符串的rad数组备用。

考虑情况3，怎样的扭动回文串会最长？观察发现，如果在插入特殊字符后枚举扭动回文串的中心，那么它一定会在当前串里左右延伸到最长才进入另一个串。

至于这个结论的证明，假设没有扩展完而达到了最长扭动回文串，画图可知扩展完之后在进入不会更劣。

于是枚举中心，对左右伸展的长度二分答案，Hash验证即可。

Manacher算法插入特殊字符的预处理使得在新串中，长度为偶数的串不可能是回文串，原来的回文串变成了新的长度为奇数的回文串，不会产生新的回文串，保证了算法的正确性。

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 200005
#define ll long long
using namespace std;
const ll mod=998244353;

ll sub(ll a,ll b){a-=b;a+=a<0?mod:0;return a;}
ll mul(ll a,ll b){a=a*b%mod;return a;}

int N,Len,rad[MAXN],ra[MAXN],rb[MAXN],Ans;
ll ha[MAXN],hb[MAXN],inv[MAXN],pw[MAXN];
char a[MAXN],b[MAXN],A[MAXN],B[MAXN];

ll ksm(ll a,ll b,ll c){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%c;
		b>>=1;a=a*a%c;
	}
	return ans;
}

int manacher(char s[],int r[]){
	int i,Max=0,pos=0,ret=0,len=2*N+1;
	memset(rad,0,sizeof(rad));
	for(i=1;i<=len;i++){
		if(i>Max)rad[i]=1;
		else rad[i]=min(Max-i+1,rad[pos*2-i]);
		while(i+rad[i]<=len&&i-rad[i]>0&&s[i+rad[i]]==s[i-rad[i]])rad[i]++;
		if(Max<i+rad[i]-1)Max=i+rad[i]-1,pos=i;
		ret=max(ret,rad[i]-1);
	}
	Ans=max(ret,Ans);
	for(i=1;i<=len;i++)r[i]=rad[i];
}

bool check(int l1,int r1,int l2,int r2){
	if(l1>r1||l2>r2)return true;
	ll a,b;
	a=mul(sub(ha[r1],ha[l1-1]),inv[l1]);
	b=mul(sub(hb[l2],hb[r2+1]),inv[Len-r2+1]);
	return a==b;
}

int main(){
	int i,l,r,L,R,mid;
	scanf("%d%s%s",&N,a+1,b+1);
	for(i=1,A[1]=B[1]='@';i<=N;i++){
		A[i<<1]=a[i];B[i<<1]=b[i];
		A[i<<1|1]=B[i<<1|1]='@';
	}
	Len=N<<1|1;
	manacher(A,ra);
	manacher(B,rb);
	
	inv[0]=1;inv[1]=ksm(131,mod-2,mod);
	pw[0]=1;pw[1]=131;
	for(i=2;i<=Len;i++)inv[i]=inv[i-1]*inv[1]%mod;
	for(i=2;i<=Len;i++)pw[i]=pw[i-1]*131%mod;
	
	for(i=1;i<=Len;i++)ha[i]=(ha[i-1]+(ll)A[i]*pw[i]%mod)%mod;
	for(i=Len;i;i--)hb[i]=(hb[i+1]+(ll)B[i]*pw[Len-i+1]%mod)%mod;
	
	for(i=1;i<=Len;i++){
		if(i+ra[i]>Len||i-ra[i]<1)continue;
		l=0;r=min(i-ra[i],Len-(i+ra[i]-1));
		L=i-ra[i];R=i+ra[i];
		while(l<=r){
			mid=l+r>>1;
			if(check(L-mid,L,R-2,R+mid-2))l=mid+1;
			else r=mid-1;
		}
		Ans=max(Ans,ra[i]+l-1);
	}
	for(i=1;i<=Len;i++){
		if(i+rb[i]>Len||i-rb[i]<1)continue;
		l=0;r=min(i-rb[i],Len-(i+rb[i]-1));
		L=i-rb[i];R=i+rb[i];
		while(l<=r){
			mid=l+r>>1;
			if(check(L-mid+2,L+2,R,R+mid))l=mid+1;
			else r=mid-1;
		}
		Ans=max(Ans,rb[i]+l-1);
	}
	printf("%d\n",Ans);
}