题解 P1819 【公共子序列】

· · 题解

在窝的博客食用更佳

大家好，本蒟蒻又来写题解了。本题解可以看做对 @神之右大臣 巨佬的题解的补充。（注：本文部分内容引用自此文）

这次这道题目所使用的算法是序列自动机，其最直接的作用是查找某个字符串是否是另一个字符串的子序列。下面给大家普及一下。

首先要清楚的是，序列自动机完全不像 AC 自动机，后缀自动机 那样高大上，本质上就是一个牺牲空间换时间的字符串记忆。百度百科甚至都没有这个词条

我们定义 nxt_{i,j} 表示从字符串第 i 个位置开始，第 j 个字符首次出现的位置。可以粗略的理解成一下 C艹 代码：

string s="abcdefg",s2=s.substr(i,c.end-c-i);
nxt[i][j]=s2.find(j+'a')+i;

那么我们的预处理就很清晰了，倒着遍历更新即可：

const int inf=0x3f3f3f3f;
int nxt[N][27];
void init(char *s) {
    int l=strlen(s);
    for(int i=0;i<26;i++) nxt[l][i]=inf;
    for(int i=l-1;i>=0;i++) { //倒着枚举起点
        for(int j=0;j<26;j++) //枚举字母
            nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i]-'a']=i //更新当前位置的nxt
    }
}

查询时，我们令指针 p=-1，然后每次 p 都跳转到 nxt_{p+1,j} 的位置。如果 p 所在的 nxt 值为 inf，说明母串中不存在子串这一个字符，故返回 false：

bool find(char *t) {
    int p=-1,l=strlen(t);
    for(int i=0;i<l;i++) {
        p=nxt[p+1][t[i]-'a'];
        if(p==inf) return false;
    }
    return true;
}

那么在这道题里怎么办呢？答案是记忆化搜索。

我们令 dp[x][y][z] 为三个字符串中分别从 x,y,z 为起点的相同子序列个数。那么我们就可以枚举每一个字母，如果三个字符串中都能找到这个字母，那么记忆化，进一步 dfs 即可。也就是说，如果字母为 i 且 nxta[x][i]&nxtb[y][i]&nxtc[z][i] 那么就可以 dfs。最后，只要当前 x,y,z 不全为 0，就将 dp[x][y][z] 增加一（即当前位置这个子序列）。

最后提醒大家，千万别忘了取模！

完结撒花~

看我写的这么详细，不点个赞再走嘛？~