序列自动机(模板)

例题:P1819 公共子序列

文章

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=160;
const ll mod=1e8;
char a[N],b[N],c[N];
int nxta[N][30],nxtb[N][30],nxtc[N][30],n;
ll f[N][N][N];
void make_nxt(int nxt[][30],int len,char a[])//构造nxt数组 
{
    for(int i=len-1;i>=0;i--)
    {
        for(int j=0;j<=25;j++)   nxt[i][j]=nxt[i+1][j];
        nxt[i][a[i+1]-'a']=i+1;//一次只会更新a[i+1]-'a'的值 
    }
}
ll dfs(int x,int y,int z)
{
    if(f[x][y][z])  return f[x][y][z];
    for(int i=0;i<=25;i++)
    {
        int q=nxta[x][i],w=nxtb[y][i],e=nxtc[z][i];
        if(q&&w&&e)//都能延续下去
            f[x][y][z] = ( f[x][y][z]+dfs(q,w,e) ) % mod;
    //这里怎么理解呢?要知道dfs是到最底下一层一层返回上来
    //以q,w,e开头的子串可以接在x,y,z上,所以加上去 
    }
    if(x||y||z) f[x][y][z]=(f[x][y][z]+1)%mod;// 
    return f[x][y][z];
}
int main()
{
    cin>>n;
    scanf("%s%s%s",a+1,b+1,c+1);
    int la=strlen(a+1),lb=strlen(b+1),lc=strlen(c+1);
    make_nxt(nxta,la,a);
    make_nxt(nxtb,lb,b);
    make_nxt(nxtc,lc,c);
    cout<<dfs(0,0,0)%mod;
}