题解 P5555 【秩序魔咒】

mrsrz · 2019-09-12 19:15:51 · 题解

为啥知道有回文自动机还要写带log的std啊

为啥放那么小范围放那么大时限啊

我记得我前几天刚刚放了PAM板子啊

前置芝士：回文自动机。不懂的可以去窝的模板那儿看看。

这个题问你最长公共回文子串长度和个数。

我们对两个字符串分别建回文自动机。回文自动机中的转移边形成了一个树形结构。

走相同的转移边，得到的回文串显然是相同的。

那么我们同时对两棵树进行dfs，每次都走相同的转移边，那么走到的每个节点代表的回文串一定是公共的。

这样就可以统计最长长度了。又由于回文自动机中每个节点代表的回文串不同，所以也可以同时统计出不同最长公共回文子串个数。

回文自动机的点数是O(n)，所以总时间复杂度O(n)。

比std短，比std快，还比std好写。

Code：

#include<cstdio>
const int N=3e5+5;
char s[N],ss[N];
int mx=0,tot=0,n,m;
struct pam{
    int len[N],fail[N],ch[N][26],tot,lst,num[N];
    char s[N];
    void init(char*ss){
        tot=lst=1;
        len[1]=-1,len[0]=0,fail[0]=1;
        for(int i=1;ss[i];++i)s[i]=ss[i];
    }
    int insert(char cr,int ed){
        int c=cr-'a';
        int p=lst;
        while(s[ed]!=s[ed-len[p]-1])
        p=fail[p];
        if(!ch[p][c]){
            int np=++tot;
            len[np]=len[p]+2;
            int q;
            for(q=fail[p];s[ed]!=s[ed-len[q]-1];q=fail[q]);
            fail[np]=ch[q][c];
            num[np]=num[fail[np]]+1;
            ch[p][c]=np;
        }
        lst=ch[p][c];
        return num[lst];
    }
}p1,p2;
void dfs(int nl,int nr){
    if(mx<p1.len[nl])mx=p1.len[nl],tot=1;else
    if(mx==p1.len[nl])++tot;
    for(int i=0;i<26;++i)
    if(p1.ch[nl][i]&&p2.ch[nr][i])dfs(p1.ch[nl][i],p2.ch[nr][i]);
}
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s%s",s+1,ss+1);
    p1.init(s),p2.init(ss);
    for(int i=1;s[i];++i)
    p1.insert(s[i],i);
    for(int i=1;ss[i];++i)
    p2.insert(ss[i],i);
    dfs(0,0);
    dfs(1,1);
    printf("%d %d\n",mx,tot);
    return 0;
}