回文自动机pam

目的：类似回文Trie树+ac自动机，可以用来统计一些其他的回文串相关的量

复杂度：O(nlogn)

https://blog.csdn.net/Lolierl/article/details/99971257

https://www.luogu.org/problem/P5496

求出以每个位置结尾的回文子串个数，强制在线

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=2e6+;

struct pam_trie

{

    int ch[];

    int fail,len,num;

};

struct pam

{

    pam_trie b[maxn];

    int n,length,last,cnt,s[maxn];

    char c[maxn];

    pam()

    {

        b[].len=;b[].len=-;

        b[].fail=;b[].fail=;

        last=;

        cnt=;

    }

    void read()

    {

        scanf("%s",c+);

        length=strlen(c+);

    }

    int get_fail(int x)

    {

        while(s[n-b[x].len-]!=s[n])x=b[x].fail;

        return x;

    }

    void insert()

    {

        int p=get_fail(last);

        if(!b[p].ch[s[n]])

        {

            b[++cnt].len=b[p].len+;

            b[cnt].fail=b[get_fail(b[p].fail)].ch[s[n]];

            //b[cnt].num=b[b[cnt].fail].num+1;

            b[p].ch[s[n]]=cnt;

        }

        last=b[p].ch[s[n]];

        b[last].num=b[b[last].fail].num+;

    }

    void solve()

    {

        int k=;

        s[]=;

        for(n=;n<=length;n++)

        {

            c[n]=(c[n]-+k)%+;

            s[n]=c[n]-'a';

            insert();

            printf("%d ",b[last].num);

            k=b[last].num;

        }

    }

}P;

int main()

{

    P.read();

    P.solve();

    return ;

}

https://www.luogu.org/problem/P3649

求回文子串出现次数*长度的最大值

#include<iostream>

#include<stdio.h>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=3e5+;

struct pam_trie

{

    int ch[];

    int fail,len,sum;

};

struct pam

{

    pam_trie b[maxn];

    int n,length,last,cnt,s[maxn];

    char c[maxn];

    long long ans;

    pam()

    {

        b[].len=;b[].len=-;

        b[].fail=;b[].fail=;

        last=;

        cnt=;

    }

    void read()

    {

        scanf("%s",c+);

        length=strlen(c+);

    }

    int get_fail(int x)

    {

        while(s[n-b[x].len-]!=s[n])x=b[x].fail;

        return x;

    }

    void insert()

    {

        int p=get_fail(last);

        if(!b[p].ch[s[n]])

        {

            b[++cnt].len=b[p].len+;

            b[cnt].fail=b[get_fail(b[p].fail)].ch[s[n]];

            b[p].ch[s[n]]=cnt;

        }

        last=b[p].ch[s[n]];

        b[last].sum++;

    }

    void solve()

    {

        s[]=;

        for(n=;n<=length;n++)

        {

            s[n]=c[n]-'a';

            insert();

        }

        ans=;

        for(int i=cnt;i>;i--)

        {

            b[b[i].fail].sum+=b[i].sum;

            ans=max(ans,1ll*b[i].sum*b[i].len);

        }

        printf("%lld\n",ans);

    }

}P;

int main()

{

    P.read();

    P.solve();

}

https://www.luogu.org/problem/P4287

计算串的最长双倍回文子串的长度，tips：fail指针指向当前节点所表示的回文串的最长回文后缀

#include<stdio.h>

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=5e5+;

struct pam_trie

{

    int ch[];

    int fail,len,sum;

};

struct pam

{

    pam_trie b[maxn];

    int n,length,last,cnt,s[maxn];

    char c[maxn];

    pam()

    {

        b[].len=;b[].len=-;

        b[].fail=;b[].fail=;

        last=;cnt=;

    }

    void read()

    {

        scanf("%d",&length);

        scanf("%s",c+);

    }

    int get_fail(int x)

    {

        while(s[n-b[x].len-]!=s[n])x=b[x].fail;

        return x;

    }

    void insert()

    {

        int p=get_fail(last);

        if(!b[p].ch[s[n]])

        {

            b[++cnt].len=b[p].len+;

            b[cnt].fail=b[get_fail(b[p].fail)].ch[s[n]];

            b[p].ch[s[n]]=cnt;

        }

        last=b[p].ch[s[n]];

        b[last].sum++;

    }

    void solve()

    {

        s[]=;

        for(n=;n<=length;n++)

        {

            s[n]=c[n]-'a';

            insert();

        }

        int ans=;

        for(int i=cnt;i>;i--)

        {

            int pos=i;

            if(b[i].len%!=||b[i].len<=ans)continue;

            while(*b[pos].len>b[i].len)pos=b[pos].fail;

            if(*b[pos].len==b[i].len)ans=b[i].len;

        }

        printf("%d\n",ans);

    }

}P;

int main()

{

    P.read();

    P.solve();

    return ;

}

ICPC 2018 南京 Mediocre String Problem，用回文自动机来求出以每个位置结尾的回文子串个数，再进行exkmp

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxn=1e6+;

struct pam_trie

{

    int ch[];

    int fail,len,num;

};

int res[maxn];

char s1[maxn],s2[maxn],t[maxn];

struct pam

{

    pam_trie b[maxn];

    int n,last,cnt,s[maxn],length;

    pam()

    {

        b[].len=;b[].len=-;

        b[].fail=;b[].fail=;

        last=;

        cnt=;

    }

    int get_fail(int x)

    {

        while(s[n-b[x].len-]!=s[n])x=b[x].fail;

        return x;

    }

    int insert()

    {

        int p=get_fail(last);

        if(!b[p].ch[s[n]])

        {

            b[++cnt].len=b[p].len+;

            b[cnt].fail=b[get_fail(b[p].fail)].ch[s[n]];

            b[p].ch[s[n]]=cnt;

        }

        last=b[p].ch[s[n]];

        b[last].num=b[b[last].fail].num+;

        return b[last].num;

    }

    void solve()

    {

        s[]=;

        length=strlen(s1);

        for(n=;n<=length;n++)

        {

            s[n]=s1[n-]-'a';

            res[n-]=insert();

        }

    }

}P;

int Next[maxn],extend[maxn];

void get_next(char *s)

{

    int n=strlen(s),i,j,k=;

    for(j=;+j<n&&s[j]==s[+j];j++);

    Next[]=j;

    for(i=;i<n;i++)

    {

        int len=k+Next[k],L=Next[i-k];

        if(L<len-i)Next[i]=L;

        else

        {

            for(j=max(,len-i);i+j<n&&s[j]==s[i+j];j++);

            Next[i]=j;

            k=i;

        }

    }

    Next[]=n;

}

void ex_kmp(char *T,char *s)

{

    int n=strlen(T),m=strlen(s),i,j,k;

    for(j=;j<n&&j<m&&T[j]==s[j];j++);

    extend[]=j;

    k=;

    for(i=;i<n;i++)

    {

        int len=k+extend[k],L=Next[i-k];

        if(L<len-i)extend[i]=L;

        else

        {

            for(j=max(,len-i);j<m&&i+j<n&&s[j]==T[i+j];j++);

            extend[i]=j;

            k=i;

        }

    }

}

int main()

{

    scanf("%s",s1);

    scanf("%s",t);

    int lens=strlen(s1);

    reverse(s1,s1+lens);

    for(int i=;i<lens;i++)s2[i]=s1[i];

    s2[lens]='\0';

    get_next(t);

    ex_kmp(s2,t);

    long long ans=;

    P.solve();

    for(int i=;i<lens;i++)

    {

        ans+=1ll*extend[i]*res[i-];

    }

    printf("%lld\n",ans);

    return ;

}

...

巴特西

回文自动机pam

最新文章

热门文章