题目描述

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

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

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull p=131;
string s;
int t,ans;
ull power[1000005],hash1[1000005],hash2[1000005];
int main()
{
	power[0]=1;
	for(int i=1;i<=1000000;i++) power[i]=power[i-1]*p;
	while(cin>>s)
	{
		t++;ans=0;
		if(s=="END") return 0;
		s=" "+s;
		int n=s.length()-1;
		for(int i=1;i<=n;i++) hash1[i]=hash1[i-1]*p+s[i];
		for(int i=n;i;i--) hash2[i]=hash2[i+1]*p+s[i];
		for(int i=1;i<=n;i++)
		{
			int l=0,r=n; 
			while(l<r)//奇回文串 
			{
				int mid=(l+r+1)>>1;
				if(i-mid<1||i+mid>n) r=mid-1;
				else if(hash1[i]-hash1[i-mid-1]*power[mid+1]==hash2[i]-hash2[i+mid+1]*power[mid+1]) l=mid;
				else r=mid-1;
			}
			ans=max(ans,r*2+1);
			l=0;r=n;
			while(l<r)//偶回文串
			{
				int mid=(l+r+1)>>1;
				if(i-mid<1||i+mid>n) r=mid-1;
				else if(hash1[i]-hash1[i-mid]*power[mid]==hash2[i+1]-hash2[i+mid+1]*power[mid]) l=mid;
				else r=mid-1;
			}
			ans=max(ans,r*2);
		}
		cout<<"Case "<<t<<": "<<ans<<endl;
	}
	return 0;
}	

这个菜鸡手造了几组数据都没啥问题但是交上去全WA了，求大佬hack一下（或者帮忙看看错误在哪也行），蒟蒻感激不尽qwq