题解：P4608 [FJOI2016] 所有公共子序列问题
jokersen
·
·
题解
子序列自动机：
对于一个字符串 s，记录 nxt_{i,j} 表示在下标 i 后面第一次出现字符 j 的位置，若没有则设为 0。
对于任意字符串 t，可以利用 nxt 数组 \mathcal O(|t|) 判断它是否是 s 的子序列：
-
建变量 p=0。
-
遍历 t，若当前遍历到的字符为 c，令 p\gets nxt_{p,c}。
-
若在 2 过程中出现了 p=0 的情况，那么 t 不是 s 的子序列，反之则是。
正确性显然，考虑 nxt 数组如何求出。
可以倒序遍历 s，一开始 nxt_{|s|,i}=0。
其余情况：
nxt_{i,j}=
\left\{\begin{matrix}
i+1&s_{i+1}=j\\
nxt_{i+1,j}&s_{i+1}\ne j\\
\end{matrix}\right.
转移考虑给最长公共子序列加一个字符，$S$ 为字符集。
$$
f_{i,j}=\sum_{c\in S} f_{P.nxt_{i,c},Q.nxt_{j,c}}
$$
对于 $k=1$，在 DP 过程中记录当前状态对应的子序列即可。
但子序列数量是指数级的，DP 要使用高精度。
而 $k=1$ 的情况下输出内容都是指数级的。题目虽未保证但为了使此题可过，$k=1$ 的情况下子序列数是不多的。
```cpp
#include<bits/stdc++.h>
#define getc getchar
#define V 52
#define N 3005
using namespace std;
using ll=unsigned long long;
constexpr ll B=1e18;
class Int{
private:vector<ll>a;
public:
Int(){};
Int(int x){a={x};}
void operator+=(const Int &x){
if(x.a.size()>a.size()) a.resize(x.a.size());
for(int i=0;i<x.a.size();i++) a[i]+=x.a[i];
for(int i=0;i<a.size()-1;i++) if(a[i]>=B) a[i]-=B,a[i+1]++;
if(a.back()>=B) a.back()-=B,a.emplace_back(1);
}
void print(){
printf("%llu",a.back());
for(int i=a.size()-2;~i;i--)
printf("%018llu",a[i]);
}
};
class SSAM{
private:int nxt[N][V];
public:
const int *operator[](int x){return nxt[x];}
void build(const string &s){
for(int i=s.size()-1;~i;i--)
memcpy(nxt[i],nxt[i+1],sizeof nxt[i]),
nxt[i][s[i]<'a'?s[i]-'A':s[i]-'a'+26]=i+1;
}
}P,Q;
bool vis[N][N];
string s;char str[N];
int n,m,op;Int f[N][N];
void DP(int x,int y){
if(vis[x][y]) return;
f[x][y]=vis[x][y]=true;for(int i=0;i<V;i++)
if(P[x][i]&&Q[y][i]) DP(P[x][i],Q[y][i]),
f[x][y]+=f[P[x][i]][Q[y][i]];
}
int dfs(int x,int y){
int res=1;puts(s.c_str());for(int i=0;i<V;i++)
if(P[x][i]&&Q[y][i]) s+=i<26?i+'A':i+'a'-26,
res+=dfs(P[x][i],Q[y][i]),s.pop_back();
return res;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",str),P.build(str);
scanf("%s",str),Q.build(str);
scanf("%d",&op);
if(op) printf("%d",dfs(0,0));
else DP(0,0),f[0][0].print();
return 0;
}
```