POJ3974 Palindrome Manacher 最长回文子串模板

时间：2023-03-09 05:58:23
POJ3974 Palindrome Manacher 最长回文子串模板

这道题可以$O(nlogn)$，当然也可以$O(n)$做啦$qwq$

$O(nlogn)$的思路是枚举每个回文中心，通过哈希预处理出前缀和后缀哈希值备用，然后二分回文串的长度，具体的就是判断在长度范围内，前缀哈希值和后缀哈希值是否相等。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll unsigned long long

#define R register int

using namespace std;

namespace Fread {

    static char B[<<],*S=B,*D=B;

    #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

    inline int g() {

        R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

        do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

    }

}using Fread::g;

const int B=,N=;

int t,ans;

ll h1[N],h2[N],p[N];

char s[N];

inline ll H1(int l,int r) {return h1[r]-h1[l-]*p[r-l+];}

inline ll H2(int l,int r) {return h2[l]-h2[r+]*p[r-l+];}

signed main() {

#ifdef JACK

    freopen("NOIPAK++.in","r",stdin);

#endif

    p[]=; for(R i=;i<=N-;++i) p[i]=p[i-]*B;

    while() { ans=; ++t;

        scanf("%s",s+); R len=strlen(s+);

        if(len==&&s[]=='E'&&s[]=='N'&&s[]=='D') break;

        for(R i=;i<=len;++i) h1[i]=h1[i-]*B+(s[i]^)+;

        for(R i=len;i>=;--i) h2[i]=h2[i+]*B+(s[i]^)+;

        for(R p=;p<=len;++p) {

            register int l=,r=min(p-,len-p);

            while(l<r) {

                register int md=l+r+>>;

                if(H1(p-md,p-)==H2(p+,p+md)) l=md;

                else r=md-;

            } ans=max(ans,l*+);

            l=,r=min(p-,len-p+);

            while(l<r) {

                register int md=l+r+>>;

                if(H1(p-md,p-)==H2(p,p+md-)) l=md;

                else r=md-;

            } ans=max(ans,l*);

        } printf("Case %d: %d\n",t,ans);

    }

}

还有一个$Manacher$算法，可以在$O(n)$时间里解决这个问题，详见这位大佬的博客

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define R register int

using namespace std;

namespace Fread {

    static char B[<<],*S=B,*D=B;

    #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

    inline int g() {

        R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

        do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

    }

}using Fread::g;

const int N=;

char s[N<<],str[N<<];

int len[N<<],l;

inline void getstr() {

    R k=; str[k]='$';

    for(R i=;i<=l;++i) str[++k]='#',str[++k]=s[i];

    str[++k]='#'; l=k;

}

inline void Manacher() {

    getstr(); R mx=,id;

    for(R i=;i<l;++i) {

        if(mx>i) len[i]=min(len[*id-i],mx-i);//先找对称的位置，和右边界取一个min

        else len[i]=;//不包含直接设为1

        while(str[i+len[i]]==str[i-len[i]]) ++len[i];//暴力匹配

        if(len[i]+i>mx) mx=len[i]+i,id=i;//更新mx和id

    }

}

signed main() {

#ifdef JACK

    freopen("NOIPAK++.in","r",stdin);

#endif

    R t=; while() { memset(len,,sizeof(len));  ++t;

        scanf("%s",s); l=strlen(s);

        if(l==&&s[]=='E'&&s[]=='N'&&s[]=='D') break;

        Manacher(); R ans=; for(R i=;i<l;++i) ans=max(ans,len[i]);

        printf("Case %d: %d\n",t,ans-);

    }

}

洛谷上也有$manacher$的模板，可以水一下；

2019.06.10

相关文章