这是动态规划法 的典型题目,长度为row和长度为col的两个串,如何求他们的最长公共子序列。这个子序列是可以不连续的。
方法:
1 建立(row+1)*(col+1)的二维表,
2. 初始化其首行首列为零
3. 以m串为行,n串为列,那么可以逐行填写。第一行代表n串的第一个字符和m串比较, 第二行代表n串的第一和第二个字符都和m串比较,以此类推。
4. 如果是相同字符,那么就把[m-1][n-1]+1和[m-1[n]和[m][n-1]比较,填入大数。
5. 如此反复填完表,就可以得到最终结果[m][n]
很难一下子说清楚,这里就弥补一下一般书上都没有的C++程序吧:
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:
int longestSub(string sa, string sb)
{
int row = sa.size();
int col = sb.size();
vector<vector<int> > dArray;
vector<int> rowV(col+1,0);
for(int i = 0; i<row+1; i++)
{
dArray.push_back(rowV);
}
for(int r=1; r<row+1; r++)
{
for(int c=1; c<col+1; c++)
{
dArray[r][c] = max(dArray[r-1][c], dArray[r][c-1]);
if(sa[r-1]==sb[c-1])
{
dArray[r][c] = max(dArray[r-1][c-1]+1, dArray[r][c]);
}
else
{
dArray[r][c] = max(dArray[r-1][c-1], dArray[r][c]);
}
}//for(int c=1; c<col+1; c++)
}//for(int r=1; r<row+1; r++)
return dArray[row][col];
}//int longestSub(string sa, string sb)
};
int main()
{
string str1("jisnldjife");
string str2("isdklnige");
Solution solu;
cout<<solu.longestSub(str1, str2);
cout<<endl;
return 0;
}
分享到:
相关推荐
最长公共子序列的算法实现,采用递归方法。
求两个字符串的最长公共子序列.pdf
主要介绍了Python求两个字符串最长公共子序列代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
动态规划法求字符串最长公共子序列
C++求最长公共子序列!实用 花费了好长时间!!
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
利用指针来查询两个字符串的最长公共子序列,并输出的算法。
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
自己编写的C++程序,求两个字符串的最长公共字串。例如a="abcrrrerads",b="afdabcssbcrrresswrds",则结果为bcrrre
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
实现了求最长公共子序列的算法,内容简单易懂,代码也很短
求解任意两个字符串的最长公共子序列
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
最长公共子序列,求两个字符串的最长公共子序列。
主要介绍了Java基于动态规划法实现求最长公共子序列及最长公共子字符串,简单描述了动态规划法的概念、原理,并结合实例形式分析了Java使用动态规划法求最长公共子序列以及最长公共子字符串相关实现技巧,需要的朋友...
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后...
【问题描述】字符序列的子序列是指从给定字符序列中随意地(不一定要联系)去掉若干个字符...给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列,该问题是求两序列A和B的最长公共子序列(LCS)