1089 最长回文子串 V2(Manacher算法)

基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题
1089 最长回文子串 V2(Manacher算法) 收藏
1089 最长回文子串 V2(Manacher算法) 关注
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str,输出Str里最长回文子串的长度。
 
Input
输入Str(Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
相关问题
最长回文子串
回文串划分 V2
640
回文串划分
40
回文字符串
10
//O(n) manacher算法
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e6+;
int l,len,p[N<<];
char s[N],S[N<<];
void manacher(){
int ans=,id=,mx=-;
for(int i=;i<l;i++){
if(id+mx>i) p[i]=min(p[id*-i],id+mx-i);
while(i-p[i]->=&&i+p[i]+<=l&&S[i-p[i]-]==S[i+p[i]+]) p[i]++;
if(id+mx<i+p[i]) id=i,mx=p[i];
ans=max(ans,p[i]);
}
printf("%d\n",ans);
}
int main(){
scanf("%s",s);len=strlen(s);
l=-;
for(int i=;i<len;i++) S[++l]='#',S[++l]=s[i];
S[++l]='#';
manacher();
return ;
}
//O(nlogn) 字符串哈希
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef int i64;
const int N=1e6+;
int n,m,ans,a[N];char s[N];
i64 P,pow[N],hash_l[N],hash_r[N];
void get_hash(){
pow[]=;
for(int i=;i<=m;i++) pow[i]=pow[i-]*P;
for(int i=;i<=m;i++) hash_r[i]=hash_r[i-]*P+a[i];
for(int i=m;i>=;i--) hash_l[i]=hash_l[i+]*P+a[i]; }
int main(){
P=;
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++){
a[++m]='#';
a[++m]=s[i]-'A';
}
a[++m]='#';
get_hash();
int l,r,mid;
for(int i=;i<=m;i++){
l=;
if(i-<m-i) r=i;
else r=m-i+;
while(r-l>){
mid=l+r>>;
i64 hash_to_l=hash_r[i-]-hash_r[i-mid-]*pow[mid];
i64 hash_to_r=hash_l[i+]-hash_l[i+mid+]*pow[mid];
if(hash_to_l==hash_to_r) l=mid;
else r=mid;
}
ans=max(ans,l);
}
printf("%d",ans);
return ;
}

 

上一篇:springMVC文件上传大小超过限制的问题


下一篇:解决springMVC文件上传报错: The current request is not a multipart request