最长公共子序列

Posted on | In |

给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

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是两个字串长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//时间复杂度o(mn) 
#include<iostream>
#include<string.h>
#include<algorithm>
int MaxLen[100][100];
char s1[500],s2[500];
using namespace std;
int main(){
	int length1,length2;

	while(cin>>s1>>s2){
	length1=strlen(s1);
	length2=strlen(s2);
	//比较s1的前length1个字符和s2的前length2相同的字符数目 
	for(int i=0;i<=length1;i++) MaxLen[i][0]=0;
	for(int i=0;i<=length2;i++) MaxLen[0][i]=0;
	for(int i=1;i<=length1;i++){
		for(int j=1;j<=length2;j++){
			if(s1[i-1]==s2[j-1]) MaxLen[i][j]=MaxLen[i-1][j-1]+1;
			else MaxLen[i][j]=max(MaxLen[i-1][j],MaxLen[i][j-1]);
		
		}
	}
	
	cout<<MaxLen[length1][length2]<<endl;
	}
	return 0;	

}

image