题目

在这里插入图片描述

思路

这道题首先需要正着hash一次，反着再做一次hash。

其次我们要枚举一个

i

，向两边扩散枚举，截取一段字符串

直接用STL截取会使时间复杂度变高，

所以使两段hash字符串相减并用正取和反取的两段比较。

这样再二分一个扩散的距离mid，

这样就可以使时间复杂度降低到允许范围内。

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;unsigned long long f[1000010],shang[1000010],xia[1000010];long long ans=0,js;string s;int main(){   	cin>>s;	while(s!="END")	 {   	 	s=" "+s;	    long long myc=s.size();	 	f[0]=1ull,shang[0]=s[0]-97;	 	ans=0,js++;	 	for(long long i=1; i<=myc; ++i)	 	   f[i]=f[i-1]*131ull,shang[i]=shang[i-1]*131ull+(s[i]-97);		xia[myc]=0;		for(long long i=myc; i>=1; --i)		   xia[i]=xia[i+1]*131ull+(s[i]-97);		for(long long i=1; i<=myc; ++i)		 {   		 	long long l=0,r=myc,mid=0;		 	while(l<=r)		 	 {   		 	 	mid=(l+r)>>1;		 	 	if(i-mid-1<0||i+mid+1>myc)		 	 	 {   		 	 	 	r=mid-1;		 	 	 	continue;				 }				else		 	 	 if(shang[i]-shang[i-mid-1]*f[mid+1]==xia[i]-xia[i+mid+1]*f[mid+1])		 	 	   l=mid+1,ans=max(ans,mid*2+1);		 	 	 else		 	 	   r=mid-1;			 }			l=0,r=myc;			while(l<=r)		 	 {   		 	 	mid=(l+r)>>1;		 	 	if(i-mid<0||i+mid+1>myc)		 	 	 {   		 	 	 	r=mid-1;		 	 	 	continue;				 }				else		 	 	 if(shang[i]-shang[i-mid]*f[mid]==xia[i+1]-xia[i+1+mid]*f[mid])		 	 	   l=mid+1,ans=max(ans,mid*2);		 	 	 else		 	 	   r=mid-1;			 }		 }		printf("Case %lld: %lld\n",js,ans);		cin>>s;	 }	return 0;}//abcbabcbabcba abacacbaaaab

上一篇：数论大杂烩——From GDKOI2021 【数论基础】【学习笔记】

下一篇：2020-2021期末考试总结

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目

思路

代码

发表评论

最新留言

关于作者

推荐文章