COJ977 WZJ的数据结构（负二十三）

试题描述

输入一个字符串S，输出S的最长连续回文子串长度。

输入

输入一个字符串S。

输出

输出S的最长连续回文子串长度

输入示例

abacbbc

输出示例

其他说明

1<=|S|<=1000000

这就是传说中的萌萌哒马拉车算法（manacher）啦

首先为了方便处奇偶两种情况，将S重新变成新的字符串T，如abacddc变成#a#b#a#c#d#d#c#

再次为了方便处理越界，将字符串首尾加一个奇怪的不匹配字符，如将abacddc变成~#a#b#a#c#d#d#c#`

请大家想一想这样的好处

考虑暴力算法，枚举回文串中心，暴力向两边匹配

rep(,n-) {

    int t=;

    while(s[i-t]==s[i+t]) t++;

    ans=max(ans,t-);

}

这样是O(N^2)，考虑优化

我们定义P[i]表示位置i的最长匹配长度，考虑利用之前的匹配信息。

这样就是p[i]=p[2*id-i]

这样就是p[i]=mx-i

写成代码就是这样

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(s,t) for(int i=s;i<=t;i++)

#define ren for(int i=first[x];i!=-1;i=next[i])

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

char s[maxn];

int p[maxn];

int solve(char* s2) {

    int n=,id=,mx=,ans=;

    for(int i=;s2[i]!='\0';i++) s[n++]='#',s[n++]=s2[i];

    s[]='~';s[n++]='#';s[n++]='`';

    rep(,n-) {

        if(mx>i) p[i]=min(p[*id-i],mx-i);

        else p[i]=;

        while(s[i+p[i]]==s[i-p[i]]) p[i]++;

        if(i+p[i]>mx) mx=i+p[i],id=i;

        ans=max(ans,p[i]-);

    }

    return ans;

}

char s2[maxn];

int main() {

    scanf("%s",s2);

    printf("%d\n",solve(s2));

    return ;

}

为什么是O(N)的呢？

因为算法只有遇到还没有匹配的位置时才进行匹配，已经匹配过的位置不再进行匹配，所以对于T字符串中的每一个位置，只进行一次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于T的长度事实上是S的两倍，所以时间复杂度依然是线性的。

补一个PAM的（以后不能装*，将”f[np]=to[k][c];to[p][c]=np;“i写成”f[to[p][c]=np]=to[k][c];“就会T飞，因为k可能等于p）

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(s,t) for(int i=s;i<=t;i++)

#define ren for(int i=first[x];i!=-1;i=next[i])

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

char ch[maxn];

struct PAM {

    int cnt,last;

    int to[maxn][],f[maxn],l[maxn];

    PAM() {cnt=f[]=;l[]=-;}

    void extend(int c,int n) {

        int p=last;

        while(ch[n]!=ch[n-l[p]-]) p=f[p];

        if(!to[p][c]) {

            int np=++cnt,k=f[p];l[np]=l[p]+;

            while(ch[n]!=ch[n-l[k]-]) k=f[k];

            f[np]=to[k][c];to[p][c]=np;

        }

        last=to[p][c];

    }

    int solve() {

        int ans=;

        rep(,cnt) ans=max(ans,l[i]);

        return ans;

    }

}sol;

int main() {

    scanf("%s",ch+);int n=strlen(ch+);

    rep(,n) sol.extend(ch[i]-'a',i);

    printf("%d\n",sol.solve());

    return ;

}

巴特西

COJ977 WZJ的数据结构（负二十三）

最新文章

热门文章