题目链接: http://poj.org/problem?id=3974
题目:
多组询问, 每组给出一个字符串, 求该字符串最长回文串的长度
数据范围支持 $O(nlog n)$
解法一:
二分 + hash
回文串分奇数串和偶数串. 对于奇数串, 我们枚举它的中点, 二分一下这个中点可以向两边扩展多远的距离; 对于偶数串, 我们枚举它中间两个点靠左的点, 同样二分可以扩展的距离, 这样时间复杂度就是 $O(nlog n)$ 的了
说起来容易, 写起来不是很容易
解法二:
每次跑一遍 manacher 就好了
说起来容易, 写起来也很容易
解法一代码:
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cstdio>
- typedef unsigned long long ull;
- using std::string;
- using std::cin;
- using std::max;
- using std::min;
- const int N=1e6+15;
- int cas,ans;
- ull p[N],f[N],d[N];
- string ch;
- int main()
- {
- p[0]=1;
- for (int i=1;i<=N;i++) p[i]=p[i-1]*113;
- while (cin>>ch)
- {
- if (ch=="END") break;
- printf("Case %d:",++cas);
- memset(f,0,sizeof(f));
- memset(d,0,sizeof(d));
- int n=ch.size();
- for (int i=0;i<n;i++)
- {
- f[i+1]=f[i]*113+ch[i]-'a'+1;
- }
- for (int i=n;i>=1;i--)
- {
- d[i]=d[i+1]*113+ch[i-1]-'a'+1;
- }
- ans=0;
- for (int i=1;i<=n;i++)
- {
- int l=1,r=min(i,n-i+1);
- while (l<r)
- {
- int mid=l+r>>1;
- int L1=i-mid+1,R1=i;
- int L2=i,R2=i+mid-1;
- int tmp1=f[R1]-f[L1-1]*p[R1-L1+1],tmp2=d[L2]-d[R2+1]*p[R2-L2+1];
- if (tmp1==tmp2) l=mid+1;
- else r=mid;
- }
- int L1=i-l+1,R1=i;
- int L2=i,R2=i+l-1;
- int tmp1=f[R1]-f[L1-1]*p[R1-L1+1],tmp2=d[L2]-d[R2+1]*p[R2-L2+1];
- if (tmp1!=tmp2) l--;
- ans=max(ans,2*l-1);
- l=1,r=min(i,n-i);
- while (l<r)
- {
- int mid=l+r>>1;
- int L1=i-mid+1,R1=i;
- int L2=i+1,R2=i+1+mid-1;
- int tmp1=f[R1]-f[L1-1]*p[R1-L1+1],tmp2=d[L2]-d[R2+1]*p[R2-L2+1];
- if (tmp1==tmp2) l=mid+1;
- else r=mid;
- }
- L1=i-l+1,R1=i;
- L2=i+1,R2=i+1+l-1;
- tmp1=f[R1]-f[L1-1]*p[R1-L1+1],tmp2=d[L2]-d[R2+1]*p[R2-L2+1];
- if (tmp1!=tmp2) l--;
- ans=max(ans,2*l);
- }
- printf("%d\n",ans);
- }
- return 0;
- }
解法二代码:
- #include<algorithm>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- const int N=2e6+15;
- using std::string;
- using std::cin;
- using std::min;
- using std::max;
- string ch;
- char s[N];
- int hw[N];
- int main()
- {
- int cas=0;
- while (cin>>ch)
- {
- if (ch=="END") return 0;
- printf("Case %d:",++cas);
- int n=ch.size();
- memset(hw,0,sizeof(hw));
- s[0]=s[1]='#';
- for (int i=1;i<=n;i++)
- {
- s[i<<1]=ch[i-1];
- s[i<<1|1]='#';
- }
- n=n*2+2;
- s[n]=0;
- int mx=0,mid;
- for (int i=1;i<n;i++)
- {
- if (i<mx) hw[i]=min(mid+hw[mid]-i,hw[(mid<<1)-i]);
- else hw[i]=1;
- for (;s[i+hw[i]]==s[i-hw[i]];hw[i]++);
- if (hw[i]+i>mx)
- {
- mx=hw[i]+i;
- mid=i;
- }
- }
- int ans=1;
- for (int i=1;i<n;i++) ans=max(ans,hw[i]);
- printf("%d\n",ans-1);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2775228.html