非確定性有窮狀態決策自動機練習題Vol.1 A.扭動的迴文串

題目描述

\(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

樣例解釋

最佳方案中的扭動迴文串如下所示（不在迴文串中的字元用.表示）：

.BC..

..ECB

數據範圍與提示

對於\(10\%\)的數據：\(N≤100\)；

對於\(30\%\)的數據：\(N≤1000\)；

對於\(50\%\)的數據：\(N≤10000\);

對於\(100\%\)的數據：\(1≤N≤10^5\)

分析

對於只在 \(A\) 中的迴文串和只在 \(B\) 中的迴文串，我們直接拿馬拉車 \(O(n)\) 解決即可

比較難處理的是扭動迴文串的情況

顯然，對於每一個迴文串，都有一個迴文中心（在馬拉車演算法前，我們已經把所有的偶迴文串填充成了奇迴文串）

我們可以把 \(A\) 串和 \(B\) 串中的每一個字元都當作迴文中心計算貢獻

在馬拉車演算法後，我們已經求出了以 \(i\) 作為迴文中心的最長迴文半徑 \(f[i]\)

我們只需要在原來的基礎上繼續向外擴展即可

對於 \(A\) 串中的字元，我們在原串上向左擴展，在 \(B\) 串上向右擴展

對於 \(B\) 串中的字元，我們在原串上向右擴展，在 \(A\) 串上向左擴展

直接暴力去掃肯定會 \(T\) ，我們可以用二分+ \(Hash\) 將擴展的複雜度降為 \(\log(n)\)

對於 \(A\) 我們正著記錄一遍哈希值，對於 \(B\) 我們倒著記錄一遍哈希值即可

程式碼

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e6+5;
typedef unsigned long long ll;
const ll bas=233;
char a[maxn],b[maxn],ksa[maxn],ksb[maxn];
int fa[maxn],fb[maxn],n;
ll hasha[maxn],hashb[maxn],mi[maxn];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int js=0;
ll get_hasha(int l,int r){
	return hasha[r]-hasha[l-1]*mi[r-l+1];
}
ll get_hashb(int l,int r){
	return hashb[l]-hashb[r+1]*mi[r-l+1];
}
//取哈希值
int solvea(int id){
	int l=id-fa[id]+1,r=id+fa[id]-1;
	int nl=0,nr=min(l-1,n-r),nmids;
	while(nl<=nr){
		nmids=(nl+nr)>>1;
		if(get_hasha(l-nmids,l)==get_hashb(r-2,r+nmids-2)) nl=nmids+1;
		else nr=nmids-1;
	}
	return fa[id]-1+nr;
}
int solveb(int id){
	int l=id-fb[id]+1,r=id+fb[id]-1;
	int nl=0,nr=min(l-1,n-r),nmids;
	while(nl<=nr){
		nmids=(nl+nr)>>1;
		if(get_hasha(l-nmids+2,l+2)==get_hashb(r,r+nmids)) nl=nmids+1;
		else nr=nmids-1;
	}
	return fb[id]-1+nr;
}
//對於兩個串分別二分
int main(){
	n=read();
	scanf("%s%s",ksa+1,ksb+1);
	n=n*2+1;
	a[0]='$',b[0]='$';
	for(int i=1;i<=n;i++){
		if(i&1) a[i]='#';
		else a[i]=ksa[i/2];
	}
	for(int i=1;i<=n;i++){
		if(i&1) b[i]='#';
		else b[i]=ksb[i/2];
	}
	mi[0]=1;
	for(int i=1;i<=n;i++){
		mi[i]=mi[i-1]*bas;
		hasha[i]=hasha[i-1]*bas+a[i];
	}
	for(int i=n;i>=1;i--){
		hashb[i]=hashb[i+1]*bas+b[i];
	}
	//預處理哈希值
	int mids=0,r=0,ans=0;
	for(int i=1;i<=n;i++){
		if(i<=r) fa[i]=min(fa[mids*2-i],r-i+1);
		while(a[i+fa[i]]==a[i-fa[i]]) fa[i]++;
		if(i+fa[i]-1>r){
			r=i+fa[i]-1,mids=i;
			ans=max(ans,fa[i]-1);
		}
	}
	mids=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r) fb[i]=min(fb[mids*2-i],r-i+1);
		while(b[i+fb[i]]==b[i-fb[i]]) fb[i]++;
		if(i+fb[i]-1>r){
			r=i+fb[i]-1,mids=i;
			ans=max(ans,fb[i]-1);
		}
	}
	//馬拉車
	for(int i=1;i<=n;i++){
		ans=max(ans,solvea(i));
		ans=max(ans,solveb(i));
	}
	printf("%d\n",ans);
	return 0;	
}

Tags: 基礎--二分查找字元串--哈希字元串--迴文串（馬拉車演算法）