一道字符串题，比赛的时候太困了，一开始先想着去搜搜有没有什么结论 \(+\) 板子往上面套了……

其实 \(12:00\) 的时候发现这个是 \(hash\) 了，然而太困了没写动，还 \(WA\) 了

Description

link

给定一个字符串。要求选取他的一个前缀(可以为空)和与该前缀不相交的一个后缀(可以为空)拼接成回文串，且该回文串长度最大。求该最大长度。

多组数据。保证 \(\sum |s|\leq 10^6\)

Solution

首先是个 \(O(n)\) 题吧，之后发现回文串，考虑 \(hash\)

我们发现答案可能由几部分组成：

1.直接看两头的回文

2.删掉两头的回文之后的字符串的最长的回文前缀 \(or\) 后缀

（脑子清醒的时候这玩意好简单）

第一部分略

第二部分直接上 \(hash\)

附：判断一个字符串是否回文的 \(O(1)\) 做法（那个预处理忽略谢谢）

res=(hash[r]-hash[l-1]*pow[r-l+1]%mod+mod)%mod;

记前缀后缀两个 \(hash\) 值，然后每次判断一下就 \(OK\) 咯

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=1e6+10,base=2333333,mod=1e9+9;
	int pre[N],suf[N],p[N];
	char s[N]; 
	inline bool check(int l,int r)
	{
		int res1=(pre[r]-pre[l-1]*p[r-l+1]%mod+mod)%mod;
		int res2=(suf[l]-suf[r+1]*p[r-l+1]%mod+mod)%mod;
		return res1==res2;
	}
	inline void work()
	{
		scanf("%s",s+1); int len=strlen(s+1),k=0;
		while(k<len/2&&s[k+1]==s[len-k]) ++k; 
		pre[k]=suf[len-k+1]=0;
		for(int i=k+1;i<=len-k;++i) pre[i]=pre[i-1]*base+s[i],pre[i]%=mod;
		for(int i=len-k;i>k;--i) suf[i]=suf[i+1]*base+s[i],suf[i]%=mod;
		for(int now=len-(k<<1);now>=0;--now)
		{
			if(check(k+1,k+now)) 
			{
				for(int i=1;i<=k+now;++i) printf("%c",s[i]);
				for(int i=len-k+1;i<=len;++i) printf("%c",s[i]);
				return puts(""),void();
			}
			if(check(len-k-now+1,len-k))
			{
				for(int i=1;i<=k;++i) printf("%c",s[i]);
				for(int i=len-k-now+1;i<=len;++i) printf("%c",s[i]);
				return puts(""),void(); 
			 } 
		 } 
		return ;
	}
	signed main()
	{
		p[0]=1; for(int i=1;i<N;++i) p[i]=p[i-1]*base%mod; 
		int T=read(); while(T--) work();
		return 0;
	}
}
signed main(){return yspm::main();} 

Codeforces1326D Prefix-Suffix Palindrome

原文：https://www.cnblogs.com/yspm/p/12548054.html