为了说明目的，需要编写程序，得到最长的公共子程序。
最长公共子串也称为最长公共子串，它不必是连续的。 在英语中简称为LCS(Longestcommonsubsequence )。 这定义了一个序列s分别是2个以上已知序列的子序列，在满足该条件的所有序列中最长时，s被称为已知序列的最长公共子序列。 在第一行中，输入整数n(0n100 )以表示要测量的数据集的数量
然后，各组的数据有两行，分别是要测量的两组字符串。 每个字符串的长度不超过1000。 对于每组输出测试数据，输出表示最大公共子序列长度的整数。 每组的结果占一行。
样品输入
2
asdf
adfsd
123abc
abc123abc
样品输出
3
6
解题思路：动态规划，先按二维数组规划。 首先，将第1列和第1列设为0，表示还没有公共部分。
因此，请注意，字符串并不包含在数组中，而是仅作为示例。
然后，可以进行遍历。 (在此，将二维数组名称作为dp。 ) a(I )==b ) j )时，dp ) I，j )=DP(I-1，j-1 ) 1； 否则dp[i，j]=max(DP[I-1][j]，dp[i][j-1] )。
添加和添加dp[i-1][j-1] 1，因为在此之前他可能具有相同的部分； a[i]！=b[j]只是加上前面公共部分最长的东西。
一行一行。
# include iostream # include cstdio # include cstring # include algorithm # includestringusingnamespacestd； int main () { int n； int i，j，alen，blen； int dp[100][100]； 字符串a； 字符串b； int p； cinn； for(p=1； p=n； p () { cinab； alen=a.size (； blen=b.size (； for(I=Alen； i0； I----a[I]=a[I-1]； for(I=Blen； i0； I--； b[I]=b[I-1]； for(I=0； i=alen； I ) { dp[0][i]=0； (for ) I=0； i=blen； I ) { dp[i][0]=0； (for ) I=1； i=blen； I ) for(j=1； j=alen； j({DP[I][j]=b[I]==a[j]？ DP [ I-1 ] [ j-1 ] 13360 max (DP [ I-1 ] [ j ]，dp[i][j-1] )； }printf('%d(n )，dp[i-1][j-1]； } return 0； }