求S串与T串的 最长公共子序列 的 长度 及其 个数.
动态规划递推式：
\[ f(i,j)=\max\left\{ f(i-1,j), f(i,j-1) \right\} \quad (S_i\neq T_j) \]
\[ f(i,j)=\max\left\{\text{ $^{(\varphi)}$ } f(i-1,j), f(i,j-1), \text{ $^{(\lambda)}$ } f(i-1,j-1) \right\} \quad (S_i= T_j) \]
\[ g(i,j)= g(i-1,j) + g(i,j-1) - g(i-1, j-1) \quad (S_i\neq T_j\text{ and }\varphi) \]
\[ g(i,j)= g(i-1,j) + g(i,j-1) + g(i-1, j-1) \quad (S_i= T_j\text{ and }\lambda) \]
#include <cstdio>
#include <cstring>
#include <algorithm>
const int mod=100000000;
char S[5003], T[5003];
int sl, tl;
int f[2][5003], g[2][5003];
int main() {
scanf("%s", S+1);
scanf("%s", T+1);
sl=strlen(S+1)-1;
tl=strlen(T+1)-1;
for (register int i=0; i<=tl; ++i) g[0][i]=1;
for (register int i=1; i<=sl; ++i) {
g[i&1][0]=1;
for (register int j=1; j<=tl; ++j) {
g[i&1][j]=0;
f[i&1][j]=std::max(f[i&1^1][j], f[i&1][j-1]);
if (S[i]==T[j]) f[i&1][j]=std::max(f[i&1][j], f[i&1^1][j-1]+1);
if (f[i&1][j]==f[i&1^1][j]) g[i&1][j]+=g[i&1^1][j];
if (f[i&1][j]==f[i&1][j-1]) g[i&1][j]+=g[i&1][j-1];
if (S[i]==T[j] && f[i&1][j]==f[i&1^1][j-1]+1) g[i&1][j]+=g[i&1^1][j-1];
if (S[i]!=T[j] && f[i&1][j]==f[i&1^1][j-1]) g[i&1][j]-=g[i&1^1][j-1];
g[i&1][j]=(g[i&1][j] + mod) % mod;
}
}
printf("%d\n%d\n", f[sl&1][tl], g[sl&1][tl]);
return 0;
}