manacher + 哈希求条
查看原帖
manacher + 哈希求条
1164775
Jadonyzx楼主2024/12/31 15:01
#include<bits/stdc++.h>
#define int unsigned long long
#define maxn 2000010
using namespace std;
int n,tot,r,p,ans;
char a[500010],s[maxn];
int dp[maxn];
int maxr[maxn];
int h[maxn],pre[maxn],suf[maxn],mul[maxn];
int Pre[maxn],Suf[maxn],uid[maxn];
const int base=131;
inline int HASH(int l,int r){return pre[r]-(pre[l-1]*mul[r-l+1]);}
inline int HASHbk(int l,int r){return suf[l]-(suf[r+1]*mul[r-l+1]);}
signed main(){
	cin>>n;mul[0]=1;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)pre[i]=pre[i-1]*base+a[i]-'a'+1;
	for(int i=n;i>=1;--i)suf[i]=suf[i+1]*base+a[i]-'a'+1;
	for(int i=1;i<=n+1;++i)mul[i]=mul[i-1]*base;
	s[++tot]='@';s[0]=s[tot+1]='@';
	for(int i=1;i<=n;++i)s[++tot]=a[i],uid[tot]=i,s[++tot]='@';
	for(int i=1;i<=tot;++i){
		if(i>r)while(s[i+dp[i]]==s[i-dp[i]])++dp[i];
		else{
			int j=p*2-i;
			dp[i]=min(r-i,dp[j]);
			while(s[i+dp[i]]==s[i-dp[i]])++dp[i];
		}
		if(i+dp[i]>r){
			r=i+dp[i];
			p=i;
		}
	}
	for(int id=1;id<=tot;++id){
		if(s[id]!='@')continue;
		int l=id-dp[id]+1+1;l=uid[l];
		int r=id+dp[id]-1-1;r=uid[r];int rr=r;
		if(l>=r)continue;
		if((r-l+1)%4!=0)continue;
		r=(l+r)/2;
		if(HASH(l,(l+r)/2)==HASHbk((l+r)/2+1,r))ans=max(ans,rr-l+1);
	}
	cout<<(ans);
	return 0;
}
2024/12/31 15:01
加载中...