loj2073 「JSOI2016」扭动的回文串

ref

主要是要理解“撑到“最长这个概念

（为啥我的代码这么长QAQ
#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;

}
巴特西

loj2073 「JSOI2016」扭动的回文串

最新文章

热门文章
