后缀自动机&序列自动机综合

时间：2024-10-13 18:35:44

好像序列自动机还没有写过…

串长为n的串共有n+1个节点，除了串中的n个节点，还有一个空的根节点放在串首。每个节点至多有26条出边，每条边连向它之后的第一个字符。

串中的任意一个子序列对应了一条根到某个节点的路径。且每条路径对应一个不同的子序列。

每个节点的parent是这个字母上一次出现的位置。更新只要沿parent指针扫描即可。

FJOI2016 所有公共子序列问题

这题暴力建trie能过80真是悲伤（因为按FJOI命题风格这题没有写数据范围

建完序列自动机暴力DP即可

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <limits>

#include <set>

#include <map>

using namespace std;

#define SZ 3333

int ys[2333],fys[2333];

#define M 60

struct Seq_A_M

{

int par[SZ],ch[SZ][62],lst[62],C,rot;

Seq_A_M()

{

    C=rot=1;

    for(int i=0;i<M;i++) lst[i]=rot;

}

void ins(char c)

{

    ++C; par[C]=lst[c];

    for(int i=0;i<M;i++)

    {

        for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;

    }

    lst[c]=C;

}

}S_A,S_B;

int n,m;

typedef long long ll;

ll dp[SZ][SZ];

char x[SZ],y[SZ];

ll getdp(int a,int b)

{

    if(!a||!b) return 0;

    if(dp[a][b]>=0) return dp[a][b];

    long long ans=1;

    for(int i=0;i<M;i++) ans+=getdp(S_A.ch[a][i],S_B.ch[b][i]);

    return dp[a][b]=ans;

}

char s[233333];

void tryy(int a,int b,int cl)

{

    if(!a||!b) return;

    s[cl]=0; printf("%s\n",s);

    for(int i=0;i<M;i++)

    {

        s[cl]=fys[i]; tryy(S_A.ch[a][i],S_B.ch[b][i],cl+1);

    }

}

int main()

{

    for(int i='A';i<='Z';i++) ys[i]=i-'A', fys[i-'A']=i;

    for(int i='a';i<='z';i++) ys[i]=i-'a'+26, fys[i-'a'+26]=i;

    int k=0;

    scanf("%d%d%s%s%d",&n,&m,x,y,&k);

    for(int i=0;i<n;i++) S_A.ins(ys[x[i]]);

    for(int i=0;i<m;i++) S_B.ins(ys[y[i]]);

    if(k==1) tryy(1,1,0);

    memset(dp,-1,sizeof(dp));

    printf("%lld\n",getdp(1,1));

}

四校联考 公共串问题

还是暴力DP。注意一些细节。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <limits>

#include <set>

#include <map>

using namespace std;

int MOD=998244353;

#define SZ 4008

#define S 26 //字符集

struct AM

{

int rot,ch[SZ][S],C,cnt[SZ];

};

struct SeqAM: public AM

{

int par[SZ],lst[S];

SeqAM()

{

    C=rot=1;

    for(int i=0;i<S;i++) lst[i]=rot;

}

void ins(char c)

{

    ++C; par[C]=lst[c];

    for(int i=0;i<S;i++)

    {

        for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;

    }

    lst[c]=C;

}

void getcnt()

{

    for(int i=1;i<=C;i++) cnt[i]=1;

    for(int i=C;i>=1;i--)

    {

        for(int j=0;j<S;j++) cnt[i]+=cnt[ch[i][j]], cnt[i]%=MOD;

    }

}

}SeqA,SeqB;

struct SufAM: public AM

{

int ml[SZ],fail[SZ],lst,cl,qzh[SZ],od[SZ];

SufAM() {C=lst=rot=1; cl=0;}

void ins(char c)

{

    int x=++C,len=++cl,p=lst;

    lst=x; ml[x]=len;

    for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=x;

    if(!p) fail[x]=rot;

    else if(ml[ch[p][c]]==ml[p]+1) fail[x]=ch[p][c];

    else

    {

        int chh=ch[p][c],cm=++C;

        ml[cm]=ml[p]+1; fail[cm]=fail[chh];

        for(int i=0;i<S;i++) ch[cm][i]=ch[chh][i];

        fail[chh]=fail[x]=cm;

        for(;ch[p][c]==chh;p=fail[p]) ch[p][c]=cm;

    }

}

void getcnt()

{

    for(int i=0;i<SZ;i++) qzh[i]=0;

    for(int i=1;i<=C;i++) qzh[ml[i]]++;

    for(int i=1;i<SZ;i++) qzh[i]+=qzh[i-1];

    for(int i=1;i<=C;i++) od[qzh[ml[i]]--]=i;

    for(int i=1;i<=C;i++) cnt[i]=1;

    for(int i=C;i>=1;i--)

    {

        for(int j=0;j<S;j++) cnt[od[i]]+=cnt[ch[od[i]][j]], cnt[od[i]]%=MOD;

    }

}

}SufA,SufB;

void prtat(AM& s)

{

    for(int i=1;i<=s.C;i++)

    {

        for(int j=0;j<S;j++) if(s.ch[i][j]) printf("%d->%d[label=%c];\n",i,s.ch[i][j],j+'a');

    }

}

AM *cur,*curb;

int dp2[SZ][SZ];

int dfs(int a,int b)

{

    if(!a) return 0;

    if(!b) return cur->cnt[a];

    if(dp2[a][b]>=0) return dp2[a][b];

    int ans=0;

    for(int i=0;i<S;i++) ans+=dfs(cur->ch[a][i],curb->ch[b][i]), ans%=MOD;

    return dp2[a][b]=ans;

}

int getdp(AM& a,AM& b)

{

    cur=&a; curb=&b;

    for(int i=1;i<=a.C;i++)

        for(int j=1;j<=b.C;j++) dp2[i][j]=-1;

    dfs(a.rot,b.rot);

    return dp2[a.rot][b.rot];

}

char A[SZ],B[SZ];

void prt(int a)

{

    a=(a%MOD+MOD)%MOD;

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

}

int main()

{

    scanf("%s%s",A,B);

    for(int i=0;A[i];i++) SeqA.ins(A[i]-'a'), SufA.ins(A[i]-'a');

    for(int i=0;B[i];i++) SeqB.ins(B[i]-'a'), SufB.ins(B[i]-'a');

    SeqA.getcnt(); SeqB.getcnt();

    SufA.getcnt(); SufB.getcnt();

    int AseqBseq=getdp(SeqA,SeqB);

    int AseqBsuf=getdp(SeqA,SufB);

    int AsufBseq=getdp(SufA,SeqB);

    int AsufBsuf=getdp(SufA,SufB);

    prt(AsufBsuf);

    prt(AsufBseq);

    prt(AseqBsuf);

    prt(AseqBseq);

}

bzoj4032 最短不公共子串

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <limits>

#include <set>

#include <map>

using namespace std;

int MOD=998244353;

#define SZ 4008

#define S 26 //字符集

struct AM

{

int rot,ch[SZ][S],C,cnt[SZ];

};

struct SeqAM: public AM

{

int par[SZ],lst[S];

SeqAM()

{

    C=rot=1;

    for(int i=0;i<S;i++) lst[i]=rot;

}

void ins(char c)

{

    ++C; par[C]=lst[c];

    for(int i=0;i<S;i++)

    {

        for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;

    }

    lst[c]=C;

}

void getcnt()

{

    for(int i=1;i<=C;i++) cnt[i]=1;

    for(int i=C;i>=1;i--)

    {

        for(int j=0;j<S;j++) cnt[i]+=cnt[ch[i][j]], cnt[i]%=MOD;

    }

}

}SeqA,SeqB;

struct SufAM: public AM

{

int ml[SZ],fail[SZ],lst,cl,qzh[SZ],od[SZ];

SufAM() {C=lst=rot=1; cl=0;}

void ins(char c)

{

    int x=++C,len=++cl,p=lst;

    lst=x; ml[x]=len;

    for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=x;

    if(!p) fail[x]=rot;

    else if(ml[ch[p][c]]==ml[p]+1) fail[x]=ch[p][c];

    else

    {

        int chh=ch[p][c],cm=++C;

        ml[cm]=ml[p]+1; fail[cm]=fail[chh];

        for(int i=0;i<S;i++) ch[cm][i]=ch[chh][i];

        fail[chh]=fail[x]=cm;

        for(;ch[p][c]==chh;p=fail[p]) ch[p][c]=cm;

    }

}

void getcnt()

{

    for(int i=0;i<SZ;i++) qzh[i]=0;

    for(int i=1;i<=C;i++) qzh[ml[i]]++;

    for(int i=1;i<SZ;i++) qzh[i]+=qzh[i-1];

    for(int i=1;i<=C;i++) od[qzh[ml[i]]--]=i;

    for(int i=1;i<=C;i++) cnt[i]=1;

    for(int i=C;i>=1;i--)

    {

        for(int j=0;j<S;j++) cnt[od[i]]+=cnt[ch[od[i]][j]], cnt[od[i]]%=MOD;

    }

}

}SufA,SufB;

void prtat(AM& s)

{

    for(int i=1;i<=s.C;i++)

    {

        for(int j=0;j<S;j++) if(s.ch[i][j]) printf("%d->%d[label=%c];\n",i,s.ch[i][j],j+'a');

    }

}

int dep[SZ][SZ];

int qa[SZ*SZ],qb[SZ*SZ];

int bfs(AM& a,AM& b)

{

    memset(dep,0,sizeof(dep));

    int h=0,t=1; qa[0]=a.rot; qb[0]=b.rot; dep[qa[0]][qb[0]]=1;

    while(h!=t)

    {

        int ca=qa[h],cb=qb[h]; ++h;

        for(int j=0;j<S;j++)

        {

            int _ca=a.ch[ca][j],_cb=b.ch[cb][j];

            if(dep[_ca][_cb]||!_ca) continue;

            if(!_cb) return dep[ca][cb];

            dep[_ca][_cb]=dep[ca][cb]+1;

            qa[t]=_ca; qb[t]=_cb; ++t;

        }

    }

    return -1;

}

#define prt(x) printf("%d\n",x)

char A[SZ],B[SZ];

int main()

{

    scanf("%s%s",A,B);

    for(int i=0;A[i];i++) SeqA.ins(A[i]-'a'), SufA.ins(A[i]-'a');

    for(int i=0;B[i];i++) SeqB.ins(B[i]-'a'), SufB.ins(B[i]-'a');

    SeqA.getcnt(); SeqB.getcnt();

    SufA.getcnt(); SufB.getcnt();

    int AseqBseq=bfs(SeqA,SeqB);

    int AseqBsuf=bfs(SeqA,SufB);

    int AsufBseq=bfs(SufA,SeqB);

    int AsufBsuf=bfs(SufA,SufB);

    prt(AsufBsuf);

    prt(AsufBseq);

    prt(AseqBsuf);

    prt(AseqBseq);

}

相关文章