洛谷P3856题解

Ginger_he · 2021-12-11 16:51:33 · 题解

题目描述

求 3 个字符串有多少个不同的公共子序列，不包括空序列。

题解

序列自动机模板题。dp_{i.c}=\min\left\{j\mid j>i,s_j=c\right\} 表示从第 i 个位置开始字符 c 在 s 中下一次出现的位置。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,x[105][30],y[105][30],z[105][30];
ll f[105][105][105];
char a[105],b[105],c[105];
ll dfs(int u,int v,int w)
{
    ll res=1;
    if(f[u][v][w]!=-1)
        return f[u][v][w];
    for(int i=1;i<=26;i++)
    {
        if(x[u][i]&&y[v][i]&&z[w][i])
            res+=dfs(x[u][i],y[v][i],z[w][i]);
    }
    return f[u][v][w]=res;
}
void pre(int t,int p[105][30],char s[105])
{
    for(int i=t-1;i>=0;i--)
    {
        for(int j=1;j<=26;j++)
            p[i][j]=p[i+1][j];
        p[i][s[i+1]-96]=i+1;
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    scanf("%s%s%s",a+1,b+1,c+1);
    pre(strlen(a+1),x,a);
    pre(strlen(b+1),y,b);
    pre(strlen(c+1),z,c);
    printf("%lld\n",dfs(0,0,0)-1);
    return 0;
}