简要题意
给出三个由小写英文字母组成的字符串 \(A,B,C\)。求这三个字符串的本质不同公共子序列个数。
- P1819：\(n=|A|=|B|=|C|,1 \leq n \leq 150\)，答案对 \(10^8\) 取模。
- P3856：\(1 \leq |A|,|B|,|C| \leq 100\)。
思路
对于子序列问题，我们先建出子序列自动机。这里简单介绍一下子序列自动机是什么：
对于一个字符串 \(S\)，令 \(F(i,j)\) 为 \([i+1,|S|]\) 中最小的 \(k\)，使得 \(S_k=j\)。则 \(F(i,j)\) 就是我们要求的子序列自动机。
\(F(i,j)\) 有一个 \(O(|S|W)\) 的做法（\(W\) 为 \(S\) 中字符集大小）。我们逆推，不难发现以下结论：
\[F(i,j)=\begin{cases} 0&i=|S|\\ i+1&(j=S_{i+1})\\ F(i+1,j)&(j\neq S_{i+1}) \end{cases} \]注意 \(i\) 可以为 \(0\)。此时指向的是最前的为 \(j\) 的位置。可以在字符串开头字符不同时充当相同的开头。
然后就可以 \(O(|S|W)\) 递推了。
然后我们回到本题。考虑 dp，令 \(f(i,j,k)\) 表示考虑到 \(A[i:|A|],B[j:|B|],C[k:|C|]\) 的公共子序列数。那么答案就是 \(f(0,0,0)\)。
考虑如何转移。如果 \(i,j,k\) 后继都有一个相同的字符（至于如何判断相同的字符，可以构造 \(A,B,C\) 的子序列自动机 \(F,G,H\)），那么就是一个公共子序列，可以转移。最后自己本身也是一个子序列（注意当 \(i,j,k\) 为 \(0\) 时这不是一个子序列）也就是：
\[f_{i,j,k}=[ijk \neq 0]+\sum_{s=\texttt{a}}^{\texttt{z}}[F(i,s)G(i,s)K(i,s) \neq 0]f(F(i,s),G(i,s),K(i,s)) \]然后这道题就做完了。
代码
P1819:
#include <bits/stdc++.h>
using namespace std;
const int N = 155;
int n;
string a,b,c;
int f[N][27],g[N][27],h[N][27],dp[N][N][N];
const int MOD = 1e8;
inline int M(const int &x){
return (x%MOD+MOD)%MOD;
}
inline void build(){
for(int i=n;i;i--){
for(int j=1;j<=26;j++){
f[i-1][j]=f[i][j];
g[i-1][j]=g[i][j];
h[i-1][j]=h[i][j];
}
f[i-1][a[i]-'a'+1]=i;
g[i-1][b[i]-'a'+1]=i;
h[i-1][c[i]-'a'+1]=i;
}
}
int F(int i,int j,int k){
if(dp[i][j][k]) return dp[i][j][k];
for(int s=1;s<=26;s++){
if(f[i][s] && g[j][s] && h[k][s]) dp[i][j][k]=M(dp[i][j][k]+F(f[i][s],g[j][s],h[k][s]));
}
if(i || j || k) dp[i][j][k]++;
return dp[i][j][k]=M(dp[i][j][k]);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>a>>b>>c;
a=" "+a;b=" "+b;c=" "+c;
build();
cout<<F(0,0,0)<<'\n';
return 0;
}
P3856:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int ytxy,zyb,zbzQ;
string a,b,c;
int f[N][27],g[N][27],h[N][27],dp[N][N][N];
inline int M(const int &x){
return x;
}
inline void build(){
for(int i=ytxy;i;i--){
for(int j=1;j<=26;j++){
f[i-1][j]=f[i][j];
}
f[i-1][a[i]-'a'+1]=i;
}
for(int i=zyb;i;i--){
for(int j=1;j<=26;j++){
g[i-1][j]=g[i][j];
}
g[i-1][b[i]-'a'+1]=i;
}
for(int i=zbzQ;i;i--){
for(int j=1;j<=26;j++){
h[i-1][j]=h[i][j];
}
h[i-1][c[i]-'a'+1]=i;
}
}
int F(int i,int j,int k){
if(dp[i][j][k]) return dp[i][j][k];
for(int s=1;s<=26;s++){
if(f[i][s] && g[j][s] && h[k][s]) dp[i][j][k]=M(dp[i][j][k]+F(f[i][s],g[j][s],h[k][s]));
}
if(i || j || k) dp[i][j][k]++;
return dp[i][j][k]=M(dp[i][j][k]);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>a>>b>>c;
ytxy=a.size();zyb=b.size();zbzQ=c.size();
a=" "+a;b=" "+b;c=" "+c;
build();
cout<<F(0,0,0)<<'\n';
return 0;
}