登录
← 返回首页 | 代码片段 › 6 字符串 › 6.2 Manacher › Manacher / 搜索
JSON MD

6.2 Manacher

manacher 标准700ms
18 行
CPP JSON
luogu-judger-enable-o2
C++ 17 行 CPP
// luogu-judger-enable-o2
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=22000003;
char a[N]={'$','|'},c=getchar();int r[N],mid,ans,R,n=1,i;
int main(){
    while(c>='a'&&c<='z')a[++n]=c,a[++n]='|',c=getchar();
    for(i=1;i<=n;i++){
        if(i<=R)r[i]=min(r[(mid<<1)-i],R-i+1);
        else r[i]=1;
        while(a[i-r[i]]==a[i+r[i]])r[i]++;
        if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
        ans=max(ans,r[i]-1);
    }
    printf("%d",ans);
}
manacher(仅适用于找最长回文长度) 玄学150ms
15 行
CPP JSON
luogu-judger-enable-o2
C++ 14 行 CPP
// luogu-judger-enable-o2
#include<cstdio>
char a[11550000]={'$'};int T,i,s,l,r;
int main(){
    gets(a+1);
    for(i=1;a[i];++i){
        l=r=i;
        while(a[i]==a[r+1])++r;
        i=r;
        while(a[r+1]==a[l-1])++r,--l;
        if(r-l+1>s)s=r-l+1;
    }
    printf("%d",s);
}
已复制