LCS最长公共子序列

题目描述

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB。则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA。序列无须是连续的，重复即可。

解题思路

• 暴力遍历
• 动态规划

暴力遍历

字符串1：BDCABA
字符串2：ABCDBAB
自行匹配， 不看出有三种匹配最长公共子序列匹配结果：BDBA,BDAB,BCAB

Dynamic Programing

• m[i]=n[j]
lcs[i][j]=lcs[i][j]+1

• m[i]=n[j]
lcs[i][j]=max{lcs[i][j-1],lcs[i-1][j]}
  代码部分实现：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int max(int a, int b) 
{
	return (a>b)? a:b;
}

/**
 * 返回X[0...m-1]和Y[0...n-1]的LCS的长度 
 */
int lcs(string &X, string &Y, int m, int n)
{
	// 动态规划表，大小(m+1)*(n+1)
	vector<vector<int>> table(m+1,vector<int>(n+1));  

	for(int i=0; i<m+1; ++i)
	{
		for(int j=0; j<n+1; ++j)
		{
			// 第一行和第一列置0
			if (i == 0 || j == 0)
				table[i][j] = 0;

			else if(X[i-1] == Y[j-1])
				table[i][j] = table[i-1][j-1] + 1;
		 
			else
				table[i][j] = max(table[i-1][j], table[i][j-1]);
		}
	}

	return table[m][n];
}

int main()
{
	string X = "ABCBDAB";
	string Y = "BDCABA";

	cout << "The length of LCS is " << lcs(X, Y, X.length(), Y.length());
	cout << endl;
	 
	getchar();
	return 0;
}