经典面试题:最长公共子序列

  1. 云栖社区>
  2. 博客>
  3. 正文

经典面试题:最长公共子序列

龙盛国际 2013-08-23 22:39:00 浏览984
展开阅读全文

1.问题描述:

什么是最长公共子序列呢?好比一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S 称为已知序列的最长公共子序列。

    举个例子,如:有两条随机序列,如 1 3 4 5 5 ,and 2 4 5 5 7 6,则它们的最长公共子序列便是:4 5 5。

    注意最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence, LCS)的区别:子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的顺序,而从序列中去掉任意的元素而获得的新序列;更简略地说,前者(子串)的字符的位置必须连续,后者(子序列LCS)则不必。比如字符串acdfg同akdfc的最长公共子串为df,而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。下文具体描述。

2.解决思路:

2.1穷举法

2.2动态规划法

用动态规划法首先要判断该问题是否符合动态规划法的条件,

 (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

   (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

3.源码:

// LCSTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

void LCS(string str1,string str2)
{
	int len1 = str1.length();
	int len2 = str2.length();
	//int **dp = new int[len1+1][len2+1];
	vector<vector<int> > dp(len1+1,vector<int>(len2+1));
	
	//动态规划初始值	
	for(int j = 0;j <= len2;j++)
		dp[0][j] = 0;
	for(int i = 0;i <=len1;i++)
		dp[i][0] = 0;

	for(int i = 0;i < len1;i++)
		for(int j = 0;j < len2;j++)
		{
			if(str1.at(i) == str2.at(j))
			{
				dp[i+1][j+1]= dp[i][j]+1;				
			}
			else if(dp[i][j+1] > dp[i+1][j])
				dp[i+1][j+1] = dp[i][j+1];
			else 
				dp[i+1][j+1] = dp[i+1][j];
		}
		cout<<"最长公共子序列长度为:"<<dp[len1][len2]<<endl;

		int ti = 0;
		int tj = 0;
		while(ti<len1 && tj<len2 )
		{
			if(str1.at(ti) == str2.at(tj))
			{
				cout<<str1.at(ti)<<" ";
				ti++;
				tj++;
			}
			else if(dp[ti+1][tj] >= dp[ti][tj+1])
				ti++;
			else
				tj++;
		}
}
int _tmain(int argc, _TCHAR* argv[])
{
	string str1 = "asddgflsksdjflkdf";
	string str2 = "sdflsdzf";
	LCS(str1,str2);
	return 0;
}



网友评论

登录后评论
0/500
评论
龙盛国际
+ 关注