洛谷P4324 扭动的回文串

传送门

题目描述

JYY有两个长度均为 NN 的字符串 AA 和 BB。

一个扭动字符串S(i,j,k)S(i,j,k) 由 AA 中的第 ii 个字符到第 jj 个字符组成的子串与 BB 中的第 jj 个字符到第 kk 个字符组成的子串拼接而成。

比如，若 A=A= ’XYZ’，B=B=’UVW’，则扭动字符串 S(1,2,3)=S(1,2,3)= ’XYVW’。

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

AA 中的一个回文串；
BB 中的一个回文串；
或者某一个回文的扭动字符串S(i,j,k)S(i,j,k)
现在 JYY 希望找出最长的扭动回文串。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制
5
ABCDE
BAECB
输出 #1复制
5

说明/提示

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

.BC…
…ECB
对于所有的数据，1 \leq n \leq 10 ^ 51≤n≤10
5

上代码：

#include
#include
#include
#include
typedef  unsigned long long ll;
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f,base=233;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int n,ans,len1[maxn],len2[maxn],len11[maxn],len22[maxn];
char a[maxn],b[maxn];
ll h1[maxn],g1[maxn],h2[maxn],g2[maxn],poww[maxn];
int Binary1(int l,int r,int now){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(h1[now]-h1[now-mid]*poww[mid]==g1[now]-g1[now+mid]*poww[mid])l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int Binary11(int l,int r,int now){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(h1[now]-h1[now-mid]*poww[mid]==g1[now+1]-g1[now+1+mid]*poww[mid])l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int Binary2(int l,int r,int now){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(h2[now]-h2[now-mid]*poww[mid]==g2[now]-g2[now+mid]*poww[mid])l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int Binary22(int l,int r,int now){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(h2[now]-h2[now-mid]*poww[mid]==g2[now+1]-g2[now+1+mid]*poww[mid])l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int Binary4(int l,int r,int nowl,int nowr){
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(h1[nowl]-h1[nowl-mid]*poww[mid]==g2[nowr]-g2[nowr+mid]*poww[mid])l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	n=read();
	scanf(" %s %s",a+1,b+1);
	poww[0]=1;
	for(int i=1;i<=n;i++)h1[i]=h1[i-1]*base+a[i],h2[i]=h2[i-1]*base+b[i],poww[i]=poww[i-1]*base;
	for(int i=n;i>=1;i--)g1[i]=g1[i+1]*base+a[i],g2[i]=g2[i+1]*base+b[i];
	for(int i=1;i<=n;i++){
		len1[i]=Binary1(1,min(i,n-i+1),i),len11[i]=Binary11(1,min(i,n-i+1),i);
		ans=max(ans,max(len1[i]*2-1,len11[i]*2));
	}
	for(int i=1;i<=n;i++){
		len2[i]=Binary2(1,min(i,n-i+1),i),len22[i]=Binary22(1,min(i,n-i+1),i);
		ans=max(ans,max(len2[i]*2-1,len22[i]*2));
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,len1[i]*2-1+Binary4(0,n-len1[i]-i+2,i-len1[i],i+len1[i]-1)*2);
		ans=max(ans,len11[i]*2+Binary4(0,n-len11[i]-i+1,i-len11[i],i+len11[i])*2);
		ans=max(ans,len2[i]*2-1+Binary4(0,n-len2[i]-i+1,i-len2[i]+1,i+len2[i])*2);
		ans=max(ans,len22[i]*2+Binary4(0,n-len22[i]-i+2,i-len22[i]+1,i+len22[i]+1)*2);
	}
	cout<<ans<<endl;
	return 0;
}

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