manacher

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;

char ss[110010],s[230000];
int p[230000];
int main(){
    while (scanf("%s",ss)!=EOF)
    {
        s[0]='$'; int pos=0;
        for (int i=0;ss[i];i++)
        {
            s[++pos]='#';
            s[++pos]=ss[i];
        }
        s[++pos]='#'; s[++pos]='\0';
        p[0]=1; p[pos]=1;
        int maxs=0,k=0;
        int ans=0;
        for (int i=1;i<pos;i++)
        {
            p[i]=0;//~~
            if (maxs>i) p[i]=min(maxs-i+1,p[2*k-i]);
            while (i+p[i]<pos&&i>p[i]&&s[i+p[i]]==s[i-p[i]]) p[i]++;
            if (maxs<i+p[i]-1) maxs=i+p[i]-1,k=i;
            ans=max(ans,p[i]);
        }
        printf("%d\n",ans-1);
    }
    return 0;
}
}}}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
char ss[110010],s[230000];
int p[230000];
int main(){
    while (scanf("%s",ss)!=EOF)
    {
        s[0]='$'; int pos=0;
        for (int i=0;ss[i];i++)
        {
            s[++pos]='#';
            s[++pos]=ss[i];
        }
        s[++pos]='#'; s[++pos]='\0';
        p[0]=1; p[pos]=1;
        int maxs=0,k=0;
        int ans=0;
        for (int i=1;i<pos;i++)
        {
            p[i]=0;//~~
            if (maxs>i) p[i]=min(maxs-i+1,p[2*k-i]);
            while (i+p[i]<pos&&i>p[i]&&s[i+p[i]]==s[i-p[i]]) p[i]++;
            if (maxs<i+p[i]-1) maxs=i+p[i]-1,k=i;
            ans=max(ans,p[i]);
        }
        printf("%d\n",ans-1);
    }
    return 0;
}