洛谷P3856 [TJOI2008] 公共子串 题解

题目链接：P3856 [TJOI2008] 公共子串

题意：

题目虽然叫公共子串，但实际上求的是公共子序列。

给定三个只有小写字母的字符串，求他们不同的公共子序列的个数（不含空串）。

两个子序列不同当且仅当这两个子序列中有字符不相同。

输入格式：

三行，字符串。

输出格式：

一行，答案。

数据范围：

字符串长度 \(\le 100\) 。

才知道这个东西叫子序列自动机，就下面这个

for(int i = len - 1; ~i; i--) {
    for(int j = 0; j < 26; j++) ch[i][j] = ch[i + 1][j];
    ch[i][s[i + 1] - 'a'] = i + 1;
}

这个东西维护了每个位置的下一个 \(c\) 字符在哪里。

那就很简单了，设 \(f(i,j,k)\) 为仅考虑「 \(i\) 到 \(|A|\) 、\(j\) 到 \(|B|\) 、\(k\) 到 \(|C|\) 」的公共子序列。

这样从 \(f(0,0,0)\) 开始搜，每次枚举字符 \(c\) ，当 \(i,j,k\) 都有下一个 \(c\) 时，

不妨记他们分别在 \(u,v,w\) ，那么这个 \(c\) 就可以拼接 \(f(u,v,w)\) 的任意公共子序列上（包括空串）。

最后减一下多算的空串就好了。如果不理解可以看看这篇递推的题解，不过我觉得记忆化搜索还蛮巧妙的。

时间复杂度 \(\mathcal{O}(n^3)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e8;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(166))

char a[N], b[N], c[N];
int ch1[N][26], ch2[N][26], ch3[N][26], f[N][N][N];
int dfs(int i, int j, int k)
{
    if(f[i][j][k] != -1) return f[i][j][k];
    int sum = 1;
    for(int l = 0; l < 26; l++)
        if(ch1[i][l] && ch2[j][l] && ch3[k][l])
            add(sum, dfs(ch1[i][l], ch2[j][l], ch3[k][l]));
    return f[i][j][k] = sum;
}
void init(int len, char *s, int ch[N][26])
{
    for(int i = len - 1; ~i; i--) {
        for(int j = 0; j < 26; j++) ch[i][j] = ch[i + 1][j];
        ch[i][s[i + 1] - 'a'] = i + 1;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f, -1, sizeof(f)); int n; cin >> n;
    cin >> (a + 1) >> (b + 1) >> (c + 1);
    init(n, a, ch1); init(n, b, ch2); init(n, c, ch3);
    cout << (dfs(0, 0, 0) - 1 + mod) % mod << '\n';
    return 0;
}

本题双倍经验：P1819 公共子序列 ，要数组开大&取模一下。

---

参考文献：

[1] https://www.luogu.com.cn/article/nbfrnfab

---

题外话：

子序列自动机也是数据结构！另外 Pio 这个衣服好可爱呀~