loj2073 「JSOI2016」扭动的回文串

#include <iostream>#include <cstdio>using namespace std;typedef unsigned long long ull;int n, pa[200005], pb[200005], ans;ull bse1[200005], bse2[200005], hsa1[200005], hsa2[200005], hsb1[200005];ull hsb2[200005];const int mod1=19260817, mod2=1e9+7;char sa[200005], sb[200005];bool iseq(int a, int b, int c, int d){ ???if(a>b) return true; ???ull sa1=0, sb1=0; ???if(a) ???????sa1 = hsa1[a-1] * bse1[b-a+1] % mod1; ???sa1 = (hsa1[b] - sa1 + mod1) % mod1; ???if(d!=n-1) ???????sb1 = hsb1[d+1] * bse1[d-c+1] % mod1; ???sb1 = (hsb1[c] - sb1 + mod1) % mod1; ???if(sa1!=sb1) ???return false; ???sa1 = sb1 = 0; ???if(a) ???????sa1 = hsa2[a-1] * bse2[b-a+1] % mod2; ???sa1 = (hsa2[b] - sa1 + mod2) % mod2; ???if(d!=n-1) ???????sb1 = hsb2[d+1] * bse2[d-c+1] % mod2; ???sb1 = (hsb2[c] - sb1 + mod2) % mod2; ???if(sa1!=sb1) ???return false; ???return true;}void manacher(char a[], int b[]){ ???int id=0, mx=0; ???for(int i=1; i<n; i++){ ???????if(i<mx) ???b[i] = min(b[2*id-i], mx-i); ???????else ???b[i] = 1; ???????while(a[i-b[i]]==a[i+b[i]]) b[i]++; ???????if(mx<i+b[i]) ??mx = i + b[i], id = i; ???????ans = max(ans, b[i]); ???}}int main(){ ???cin>>n; ???scanf("%s", sa); ???scanf("%s", sb); ???for(int i=n; i>=0; i--){ ???????sa[2*i+1] = ‘#‘; ???????sa[2*i+2] = sa[i]; ???} ???for(int i=n; i>=0; i--){ ???????sb[2*i+1] = ‘#‘; ???????sb[2*i+2] = sb[i]; ???} ???sa[0] = sb[0] = ‘$‘; ???n = 2 * (n + 1); ???bse1[0] = bse2[0] = 1; ???for(int i=1; i<n; i++){ ???????bse1[i] = bse1[i-1] * 131 % mod1; ???????bse2[i] = bse2[i-1] * 131 % mod2; ???} ???ull ff=0; ???for(int i=0; i<n; i++){ ???????ff = (ff * 131 % mod1 + sa[i]) % mod1; ???????hsa1[i] = ff; ???} ???ff = 0; ???for(int i=0; i<n; i++){ ???????ff = (ff * 131 % mod2 + sa[i]) % mod2; ???????hsa2[i] = ff; ???} ???ff = 0; ???for(int i=n-1; i>=0; i--){ ???????ff = (ff * 131 % mod1 + sb[i]) % mod1; ???????hsb1[i] = ff; ???} ???ff = 0; ???for(int i=n-1; i>=0; i--){ ???????ff = (ff * 131 % mod2 + sb[i]) % mod2; ???????hsb2[i] = ff; ???} ???manacher(sa, pa); ???manacher(sb, pb); ???ans--; ???for(int i=1; i<n; i++){ ???????int pos1=i-pa[i], pos2=i+pa[i]-2; ???????int l=0, r=min(pos1, n-pos2), mid, re; ???????while(l<=r){ ???????????mid = (l + r) >> 1; ???????????if(iseq(pos1-mid+1, pos1, pos2, pos2+mid-1)) ???????????????re = mid, l = mid + 1; ???????????else ???r = mid - 1; ???????} ???????ans = max(ans, pa[i]+re-1); ???} ???for(int i=1; i<n; i++){ ???????int pos1=i-pb[i]+2, pos2=i+pb[i]; ???????int l=0, r=min(pos1, n-pos2), mid, re; ???????while(l<=r){ ???????????mid = (l + r) >> 1; ???????????if(iseq(pos1-mid+1, pos1, pos2, pos2+mid-1)) ???????????????re = mid, l = mid + 1; ???????????else ???r = mid - 1; ???????} ???????ans = max(ans, pb[i]+re-1); ???} ???cout<<ans<<endl; ???return 0;}