Description
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希望找出最长的扭动回文串。
Input
第一行包含一个正整数N。
第二行包含一个长度为N的由大写字母组成的字符串A。
第三行包含一个长度为N的由大写字母组成的字符串B。
1≤N≤10^5
Output
输出的第一行一个整数，表示最长的扭动回文串。
Sample Input
5
ABCDE
BAECB
Sample Output
5
HINT
最佳方案中的扭动回文串如下所示（不在回文串中的字符用.表示）：
.BC..
..ECB
首先我们需要知道扭动的回文串的两种情况
1、它为A串或B串的子串
2、它的对称中心有一部分在A串或B串
对于第一种情况十分好写，这里就不再多说，主要是讲讲第二种情况
对于 第二种情况而言，我们首先枚举回文串中点 i，然后找到最大能扩张的最大范围(i-p[i]~i+p[i])，若回文串的中点在A串，则A串所能继续取到的范围是(1~i-p[i]-1)，而B串中所能取到的范围是(i+p[i]~len)，若中心点在B串类似。
那么下一步我们该怎么做？二分长度。二分一个长度，然后判断A的一部分和B串的一部分是否一样
如何判断？哈希。记录哈希出来的值的前缀和，B串记录后缀和，判断的时候做类似前缀和的减法即可，记得双哈希
依然不懂？上代码
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){ ???int x=0,f=1;char ch=getchar(); ???for (;ch<‘0‘||ch>‘9‘;ch=getchar()) ?if (ch==‘-‘) ???f=-1; ???for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) ???x=(x<<1)+(x<<3)+ch-‘0‘; ???return x*f;}inline void print(int x){ ???if (x>=10) ????print(x/10); ???putchar(x%10+‘0‘);}const int N=1e5,limit=27,p1=100007,p2=233333;char A[N*2+10],B[N*2+10];int pA[N*2+10],pB[N*2+10];int sumA[2][N*2+10],sumB[2][N*2+10],g[2][N*2+10];int len,Ans;void work(char *s,int *p){ ???int Max=0,ID=0; ???for (int i=1;i<=len;i++){ ???????p[i]=Max>i?min(p[ID*2-i],Max-i):1; ???????while (s[i+p[i]]==s[i-p[i]]) ???p[i]++; ???????if (Max<p[i]+i) Max=p[ID=i]+i; ???}}bool check(int l1,int r1,int l2,int r2,int Len){ ?//哈希判断，利用前缀和 ???int x=(sumA[0][r1]-1ll*sumA[0][l1-1]*g[0][Len]%p1)%p1; ???int y=(sumB[0][l2]-1ll*sumB[0][r2+1]*g[0][Len]%p1)%p1; ???x=(x+p1)%p1,y=(y+p1)%p1; ???if (x!=y) ??return 0; ???x=(sumA[1][r1]-1ll*sumA[1][l1-1]*g[1][Len]%p2)%p2; ???y=(sumB[1][l2]-1ll*sumB[1][r2+1]*g[1][Len]%p2)%p2; ???x=(x+p2)%p2,y=(y+p2)%p2; ???return x==y;}int solve(int j,int k){ ?//二分枚举长度 ???int l=0,r=min(j,(len>>1)-k+1),ans=0; ???while (l<=r){ ???????int mid=(l+r)>>1; ???????if (check(j-mid+1,j,k,k+mid-1,mid)) l=mid+1,ans=mid; ???????else ???r=mid-1; ???} ???return ans;}int main(){ ???len=read(); ???scanf("%s%s",A+1,B+1); ???for (int i=len;i;i--) ??A[i<<1]=A[i],B[i<<1]=B[i],A[i<<1|1]=B[i<<1|1]=‘&‘; ???len=len<<1|1; ???A[0]=B[0]=‘#‘,A[1]=B[1]=‘&‘,A[len+1]=B[len+1]=‘^‘,g[0][0]=g[1][0]=1; ???work(A,pA),work(B,pB); ???for (int i=1;i<=len;i++) ???pA[i]--,pB[i]--; ?//回文串的长度会多出来一位，应该减去 ???for (int i=1;i<=len;i++) ???????Ans=max(Ans,max(pA[i],pB[i])), ??//回文串为子串的情况 ???????g[0][i]=1ll*g[0][i-1]*limit%p1, ???????g[1][i]=1ll*g[1][i-1]*limit%p2; ?//记录类似进制一样的东西 ???for (int i=2;i<len;i+=2) ???????sumA[0][i>>1]=(1ll*sumA[0][(i>>1)-1]*limit+A[i])%p1, ???????sumA[1][i>>1]=(1ll*sumA[1][(i>>1)-1]*limit+A[i])%p2; ?//记录两个哈希的前缀和，每次多出一位要乘上一个进制(limit) ???for (int i=len-1;i>1;i-=2) ???????sumB[0][i>>1]=(1ll*sumB[0][(i>>1)+1]*limit+B[i])%p1, ???????sumB[1][i>>1]=(1ll*sumB[1][(i>>1)+1]*limit+B[i])%p2; ?//由于对称，所以B串的记录要从后面开始 ???for (int i=2;i<len;i++){ ?//回文串中心在A串中的情况 ???????int l=i-pA[i],r=i+pA[i]; ???????l=(l+1)>>1,r>>=1; ???????Ans=max(Ans,pA[i]+solve(l-1,r)*2); ???} ???for (int i=2;i<len;i++){ ?//回文串中心在B串中的情况 ???????int l=i-pB[i],r=i+pB[i]; ???????l=(l+1)>>1,r>>=1; ???????Ans=max(Ans,pB[i]+solve(l,r+1)*2); ???} ???printf("%d\n",Ans); ???return 0;}