题解：P1819 公共子序列

· · 题解

Solution

对三个串建出子序列自动机，考虑在子序列自动机上 \text{DP}，设 f_{x,y,z} 表示子序列当前在三个子序列自动机上分别走到了 x,y,z 这三个状态，继续走能形成多少种子序列。

转移就为 f_{x,y,z}=1+\sum\limits_{c\in\Sigma} f_{nxt_{0,x,c},nxt_{1,y,c},nxt_{2,z,c}}。

注意这个值是包含空子序列的，所以最后答案要减去 1。

时间复杂度为 O(n^3\vert\Sigma\vert)。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
const int N=151,mod=1e8;
int nxt[3][N][26];
int n,f[N][N][N];
char s[3][N];

int read() {
    int x=0; bool f=true; char c=0;
    while (!isdigit(c) ) f&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?x:-x;
}
int solve(int x,int y,int z) {
    if (f[x][y][z]) return f[x][y][z]; f[x][y][z]=1;
    for (int i=0;i<26;i++) if (nxt[0][x][i]&&nxt[1][y][i]&&nxt[2][z][i])
    f[x][y][z]=(f[x][y][z]+solve(nxt[0][x][i],nxt[1][y][i],nxt[2][z][i]) )%mod;
    return f[x][y][z];
}
main()
{
    n=read();
    for (int i=0;i<3;i++)
    {
        scanf("%s",s[i]+1);
        for (int j=n;j;j--) {
            for (int k=0;k<26;k++)
            nxt[i][j-1][k]=nxt[i][j][k];
            nxt[i][j-1][s[i][j]-'a']=j;
        }
    }
    printf("%lld",(solve(0,0,0)+mod-1)%mod);
    return 0;
}