原題及翻譯

A subsequence of a given sequence is the given sequence with some elements (possible none) left out.
給定序列的子序列是給定序列，其中遺漏了一些元素（可能沒有元素）。
Given a sequence X = < x1, x2, …, xm >
給定序列x=<x1，x2，…，xm>
another sequence Z = < z1, z2, …, zk >
另一個序列z=<z1，z2，…，zk>
is a subsequence of X if there exists a strictly increasing sequence < i1, i2, …, ik > of indices of X such that for all j = 1,2,…,k, x ij = zj.
是x的子序列，如果x的指數存在一個嚴格遞增的序列<i1，i2，…，ik>，因此對于所有j=1，2，…，k，x ij=zj。
For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >.
例如，z=<a，b，f，c>是索引序列<1，2，4，6>的x=<a，b，c，f，b，c>的子序列。
Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
給定兩個序列x和y，問題是求x和y的最大長度公共子序列的長度。

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
程序輸入來自標準輸入。輸入中的每個數據集包含兩個表示給定序列的字符串。序列由任意數量的空格分隔。輸入數據正確。

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
對于每一組數據，程序在標準輸出上打印從一個單獨行開始的最大長度公共子序列的長度。

Sample Input

abcfbc abfcab
programming contest
abcd mnp

Sample Output

4
2
0

思路

輸入兩個串s1,s2,設MaxLen(i,j)表示:
s1的左邊i個字符形成的子串，與s2左邊的j個字符形成的子串的最長公共子序列的長度(i,j從0開始算）
MaxLen(i,j) 就是本題的“狀態”
假定 len1 = strlen(s1),len2 = strlen(s2）那么題目就是要求 MaxLen(len1,len2）
顯然：
MaxLen(n,0) = 0 ( n= 0…len1）
MaxLen(0,n) = 0 ( n= 0…len2）
遞推公式：
if ( s1[i-1] == s2[j-1] ) //s1的最左邊字符是s1[0]
MaxLen(i,j) = MaxLen(i-1,j-1) + 1;
else
MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );
時間復雜度O(mn) m,n是兩個字串

S1[i-1]!= s2[j-1]時，MaxLen(S1,S2)不會比MaxLen(S1,S2j-1) 和MaxLen(S1i-1,S2)兩者之中任何一個小，也不會比兩者都大。

代碼分析

#include <iostream> #include <cstring> using namespace std; char sz1[1000]; char sz2[1000]; int maxLen[1000][1000]; int main() {while( cin >> sz1 >> sz2 ){int length1 = strlen( sz1);int length2 = strlen( sz2);int nTmp;int i,j;for( i = 0;i <= length1; i ++ )maxLen[i][0] = 0;for( j = 0;j <= length2; j ++ )maxLen[0][j] = 0;for( i = 1;i <= length1;i ++ ){for( j = 1; j <= length2; j ++ ){if( sz1[i-1] == sz2[j-1] )maxLen[i][j] = maxLen[i-1][j-1] + 1;elsemaxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);}}cout << maxLen[length1][length2] << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Common Subsequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。