Java教程

《算法竞赛进阶指南》0x14 T3 Palindrome

本文主要是介绍《算法竞赛进阶指南》0x14 T3 Palindrome,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目传送门

题目描述

如果一个字符串正着读和倒着读是一样的,则称它是回文的。

给定一个长度为 N 的字符串 S,求他的最长回文子串的长度是多少。

题解

这也是一道经典的字符串Hash题目,要求找出最长的回文子串
我们可以枚举每一个点作为回文子串的中心点,判断从它向两侧拓展,能构成的最长回文子串是多大的。
因为回文的原因,我们需要求一遍Hash前缀和,再求一遍Hash后缀和,分别用来计算从左端点到中心的Hash值和从右端点到中心的Hash值。
由于我们从中间向两边扩展,如果当前符合回文子串,那就可以继续向外扩展,否则就不能,这个操作是可以用二分来实现减少时间复杂度的,因此总复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
所以用字符串Hash加二分就可以解决此题,特别要注意的是回文串的奇偶性,不能单只考虑一种情况。

code
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
const int P=99991;
const int M=1e9+7;
char s[N];
unsigned long long f1[N],f2[N],p1[N],p2[N];
int n;
int main()
{
	int tot=0;
	while(1)
	{
		scanf("%s",s+1);
		if(s[1]=='E'&&s[2]=='N') break;
		int maxn=0;
		tot++;
		printf("Case %d: ",tot);
		int len=strlen(s+1);
		p1[0]=1;
		for(int i=1;i<=len;i++)
		{
			f1[i]=f1[i-1]*P+s[i];
			p1[i]=p1[i-1]*P;
		}
		reverse(s+1,s+1+len);
		p2[0]=1;
		for(int i=1;i<=len;i++)
		{
			f2[i]=f2[i-1]*P+s[i];
			p2[i]=p2[i-1]*P;
		}
		int x;
		reverse(s+1,s+1+len);
		for(int i=1;i<=len;i++)
		{
			int l=1,r=min(i,len-i+1),ans=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(f1[i]-f1[i-mid]*p1[mid]==f2[len-i+1]-f2[len-i-mid+1]*p2[mid]) l=mid+1,ans=mid;
				else r=mid-1;
			}
			if(ans*2-1>maxn) maxn=ans*2-1,x=i-ans+1;
			l=0,r=min(i,len-i+1),ans=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(f1[i]-f1[i-mid]*p1[mid]==f2[len-i]-f2[len-i-mid]*p2[mid]) l=mid+1,ans=mid;
				else r=mid-1;
			}	
			if(ans*2>maxn) maxn=ans*2,x=i-ans+1;
		}
		printf("%d\n",maxn);
	}
	return 0;
}
这篇关于《算法竞赛进阶指南》0x14 T3 Palindrome的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!