题目描述
作为一名情报局特工，Nova君(2号)有着特殊的传达情报的技巧。为了避免被窃取情报，每次传达时，他都会发出两句旁人看来意义不明话，实际上暗号已经暗含其中。解密的方法很简单，分别从两句话里删掉任意多个字母，使得两句话剩余的部分相同，通过一定的删除手法，可以让剩余的部分相同且长度最大，就得到了可能的暗号。暗号可能有多个，还要进行筛选，现在情报局人手不够，希望你能助一臂之力，筛选工作不用你完成，你只需计算出暗号长度以及个数即可。（注意，字母的位置也是暗号的重要信息，位置不同的字母组成的暗号不算同一种，详见样例）
输入
多组测试数据（组数小于20）
每组数据输入两行，分别为两个字符串（只含英文字母，无空格），每个字符串以"." 结束
输出
对于每组数据，输出两行，第一行为暗号的长度，第二行为暗号的个数（答案可能很大，对个数100000000求模）
输入样例
AAAA.
AA.输出样例
2 6题目来源：http://biancheng.love/contest/17/problem/F/index
最长公共子序列的实现可参考：http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html
和之前的不同在于需要计算出最长公共子序列一共有多少个！翻看不少博客很少有提到计算最长公共子序列的个数问题
下面给出代码实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int m=100000000;//对m求模 5 int f[2][5001]= {0},g[2][5001]= {0}; 6 7 int main() 8 { 9 string s1,s2; 10 while(cin>>s1>>s2) 11 { 12 memset(f,0,sizeof(f)); 13 memset(g,0,sizeof(g)); 14 int len1=s1.size()-1,len2=s2.size()-1;//串s1,s2长度 15 16 for(int i=0; i<=len2; i++) 17 g[0][i]=1; 18 int k; 19 for(int i=1; i<=len1; i++) 20 { 21 k=i & 1;//与运算 当i是奇数时k=1,当i时偶数是k是0 22 memset(g[k],0,sizeof(g[k])); 23 memset(f[k],0,sizeof(f[k])); 24 g[k][0]=1; 25 g[!k][0]=1; 26 for(int j=1; j<=len2; j++) 27 { 28 if(s1[i-1]==s2[j-1]) 29 { 30 f[k][j]=f[!k][j-1]+1; 31 g[k][j]=g[!k][j-1]; 32 g[k][j]%=m; 33 if(f[k][j]==f[!k][j]) 34 { 35 g[k][j]+=g[!k][j]; 36 g[k][j]%=m; 37 } 38 if(f[k][j-1]==f[k][j]) 39 { 40 g[k][j]+=g[k][j-1]; 41 g[k][j]%=m; 42 } 43 } 44 else 45 { 46 if(f[!k][j]>f[k][j-1]) 47 { 48 f[k][j]=f[!k][j]; 49 g[k][j]+=g[!k][j]; 50 g[k][j]%=m; 51 } 52 if(f[!k][j]<f[k][j-1]) 53 { 54 f[k][j]=f[k][j-1]; 55 g[k][j]+=g[k][j-1]; 56 g[k][j]%=m; 57 } 58 if(f[!k][j]==f[k][j-1]) 59 { 60 f[k][j]=f[!k][j]; 61 g[k][j]+=g[!k][j]+g[k][j-1]; 62 if(f[!k][j-1]==f[k][j])g[k][j]-=g[!k][j-1]; 63 g[k][j]=(g[k][j]+3*m)%m; 64 } 65 } 66 } 67 } 68 cout<<f[k][len2]<<endl; 69 cout<<g[k][len2]<<endl; 70 } 71 }