稍微做一点吧。
好像序列自动机还没有写过…
串长为n的串共有n+1个节点，除了串中的n个节点，还有一个空的根节点放在串首。每个节点至多有26条出边，每条边连向它之后的第一个字符。
串中的任意一个子序列对应了一条根到某个节点的路径。且每条路径对应一个不同的子序列。
每个节点的parent是这个字母上一次出现的位置。更新只要沿parent指针扫描即可。
FJOI2016 所有公共子序列问题
这题暴力建trie能过80真是悲伤（因为按FJOI命题风格这题没有写数据范围
建完序列自动机暴力DP即可
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <vector> #include <limits> #include <set> #include <map> using namespace std; #define SZ 3333 int ys[2333],fys[2333]; #define M 60 struct Seq_A_M { int par[SZ],ch[SZ][62],lst[62],C,rot; Seq_A_M() { C=rot=1; for(int i=0;i<M;i++) lst[i]=rot; } void ins(char c) { ++C; par[C]=lst[c]; for(int i=0;i<M;i++) { for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C; } lst[c]=C; } }S_A,S_B; int n,m; typedef long long ll; ll dp[SZ][SZ]; char x[SZ],y[SZ]; ll getdp(int a,int b) { if(!a||!b) return 0; if(dp[a][b]>=0) return dp[a][b]; long long ans=1; for(int i=0;i<M;i++) ans+=getdp(S_A.ch[a][i],S_B.ch[b][i]); return dp[a][b]=ans; } char s[233333]; void tryy(int a,int b,int cl) { if(!a||!b) return; s[cl]=0; printf("%s\n",s); for(int i=0;i<M;i++) { s[cl]=fys[i]; tryy(S_A.ch[a][i],S_B.ch[b][i],cl+1); } } int main() { for(int i=‘A‘;i<=‘Z‘;i++) ys[i]=i-‘A‘, fys[i-‘A‘]=i; for(int i=‘a‘;i<=‘z‘;i++) ys[i]=i-‘a‘+26, fys[i-‘a‘+26]=i; int k=0; scanf("%d%d%s%s%d",&n,&m,x,y,&k); for(int i=0;i<n;i++) S_A.ins(ys[x[i]]); for(int i=0;i<m;i++) S_B.ins(ys[y[i]]); if(k==1) tryy(1,1,0); memset(dp,-1,sizeof(dp)); printf("%lld\n",getdp(1,1)); }
原文：http://www.cnblogs.com/zzqsblog/p/5371808.html