JSOI 2016 扭动的回文串（Manacher+二分答案+哈希）

发表于 |
字数统计: 900字 | 阅读时长 ≈ 4min

【JSOI2016】扭动的回文串

问题描述

JYY 有两个长度均为 $N$ 的字符串 $A$ 和 $B$。

一个「扭动字符串」$S(i,j,k)$ 由 $A$ 中的第 $i$ 个字符到第 $j$ 个字符组成的子串与 $B$ 中的第 $j$ 个字符到第 $k$ 个字符组成的子串拼接而成。
比如，若 $A=$’XYZ’，$B=$’UVW’，则扭动字符串 $S(1,2,3)=$’XYVW’。

JYY 定义一个「扭动的回文串」为如下情况中的一个：

  1. $A$ 中的一个回文串；
  2. $B$ 中的一个回文串；
  3. 或者某一个回文的扭动字符串$S(i,j,k)$

现在 JYY 希望找出最长的扭动回文串。

输入格式

第一行包含一个正整数 $N$。

第二行包含一个长度为 $N$ 的由大写字母组成的字符串 $A$。

第三行包含一个长度为 $N$ 的由大写字母组成的字符串 $B$。

输出格式

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

样例输入

5

ABCDE

BAECB

样例输出

5

提示

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

情况1，2直接Manacher就完了。

考虑情况三，先考虑回文串中心在$A$串上的情况，那么画画图容易推导出扭动的位置必然是$A$串的一个极长回文子串的一端，因此可以考虑在$Manacher$过程中，每次算出以当前点为中心的左右边界后，二分枚举通过扭曲能够拓展的长度，然后可以用哈希来判断是否能构成回文串，长度为奇或偶可以通过添加特殊字符处理。

然后如果回文串中心在$B$串上，直接将A,B串交换并且$reverse$之后再跑一遍就行了。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll Aash[N],Bash[N],Pow[N],Inv[N];
int n,Ans,rad[N];
char s[N],A[N],B[N];
ll QM(ll a,ll b)
{
	ll o=1;
	while(b)
	{
		if(b&1)o=o*a%mod;
		b>>=1;a=a*a%mod;
	}
	return o;
}
void Manacher(char x[],char y[])
{
	int i,j,k,Max=0,pos=0;
	Aash[0]=Bash[0]='$';
	for(i=1;i<=n+n;i++)
	{
		Aash[i]=(x[i]*Pow[i]%mod+Aash[i-1])%mod;
		Bash[i]=(y[i]*Inv[i]%mod+Bash[i-1])%mod;
	}
	for(i=1;i<=n+n;i++)
	{
		if(i<=Max)rad[i]=min(Max-i+1,rad[2*pos-i]);
		else rad[i]=1;
		while(i-rad[i]>0&&i+rad[i]<=n+n&&x[i-rad[i]]==x[i+rad[i]])rad[i]++;
		if(Max<i+rad[i]-1)Max=i+rad[i]-1,pos=i;
		int lp=i-rad[i],rp=i+rad[i]-2;
		int l=1,r=min(lp+1,n+n-rp+1);
		while(l<=r)
		{
			int mid=l+r>>1;
			ll t1=lp-mid>=0?(Aash[lp]-Aash[lp-mid])*Inv[lp-mid+1]%mod:Aash[lp];
			ll t2=(Bash[rp+mid-1]-Bash[rp-1])*Pow[rp+mid-1]%mod;
			t1=(t1+mod)%mod;t2=(t2+mod)%mod;
			if(t1==t2)l=mid+1;
			else r=mid-1;
		}
		Ans=max(Ans,rad[i]+r-1);
	}
}
int main()
{
	int i,j;
	scanf("%d",&n);
	scanf("%s",&s[1]);
	for(i=j=1;j<=n;j++,i+=2)A[i]=s[j],A[i-1]=A[i+1]='$';
	scanf("%s",&s[1]);
	for(i=j=1;j<=n;j++,i+=2)B[i]=s[j],B[i-1]=B[i+1]='$';
	Pow[0]=Inv[0]=1;Inv[1]=QM(13131,mod-2);
	for(i=1;i<=n+n;i++)Pow[i]=Pow[i-1]*13131ll%mod;
	for(i=2;i<=n+n;i++)Inv[i]=Inv[i-1]*Inv[1]%mod;
	Manacher(A,B);
	reverse(A,A+n+n+1);
	reverse(B,B+n+n+1);
	Manacher(B,A);
	printf("%d",Ans);
}