鏈接：點擊這里

?

?

#include<iostream> #include<algorithm> #include<stdio.h> #include<cstring> using namespace std; #define maxn 1000005 #define LL long long #define ull unsigned long long const LL P = 131; ull p[maxn+10],f[maxn],ff[maxn]; int main(){p[0]=1;for(int j=1;j<=maxn;j++){p[j]=p[j-1]*P;}string s;int tot=1;while(cin>>s){if(s=="END") break;f[0]=0,ff[0]=0;int ans=0;int len=s.size();for(int j=1;j<=len;j++){f[j]=f[j-1]*P+s[j-1]-'a'+1;}for(int j=len;j>=1;j--){ff[j]=ff[j+1]*P+s[j-1]-'a'+1;}for(int j=1;j<=len;j++){int l=1,r=min(len-j,j),mx=0;while(l<=r){ // 偶數int mid=(l+r)/2;int l1=j-mid+1,r1=j;int l2=j+1,r2=j+mid;LL ll=f[r1]-f[l1-1]*p[r1-l1+1];LL rr=ff[l2]-ff[r2+1]*p[r2-l2+1];if(ll==rr){mx=max(mx,mid);l=mid+1;}else r=mid-1;}ans=max(ans,2*mx);l=1,r=min(len-j,j-1),mx=0;while(l<=r){ //奇數int mid=(l+r)/2;int l1=j-mid,r1=j-1;int l2=j+1,r2=j+mid;LL ll=f[r1]-f[l1-1]*p[r1-l1+1];LL rr=ff[l2]-ff[r2+1]*p[r2-l2+1];if(ll==rr){mx=max(mx,mid);l=mid+1;}else r=mid-1;}ans=max(ans,2*mx+1);}//cout<<ans<<endl;printf("Case %d: %d\n",tot++,ans);}return 0; }

?

轉載于:https://www.cnblogs.com/DyLoder/p/10200569.html

總結

以上是生活随笔為你收集整理的POJ--3974 Palindrome（回文串，hash）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。