在“LD算法”中介绍了基于编辑距离的文本比较算法——LD算法。
本文介绍基于最长公共子串的文本比较算法——Needleman/Wunsch算法。
还是以实例说明:字符串A=kitten,字符串B=sitting
那他们的最长公共子串为ittn(注:最长公共子串不需要连续出现,但一定是出现的顺序一致),最长公共子串长度为4。
定义:
LCS(A,B)表示字符串A和字符串B的最长公共子串的长度。很显然,LSC(A,B)=0表示两个字符串没有公共部分。
Rev(A)表示反转字符串A
Len(A)表示字符串A的长度
A+B表示连接字符串A和字符串B
性质:
LCS(A,A)=Len(A)
LCS(A,"")=0
LCS(A,B)=LCS(B,A)
0≤LCS(A,B)≤Min(Len(A),Len(B))
LCS(A,B)=LCS(Rev(A),Rev(B))
LCS(A+C,B+C)=LCS(A,B)+Len(C)
LCS(A+B,A+C)=Len(A)+LCS(B,C)
LCS(A,B)≥LCS(A,C)+LCS(B,C)
LCS(A+C,B)≥LCS(A,B)+LCS(B,C)
为了讲解计算LCS(A,B),特给予以下几个定义
A=a1a2……aN,表示A是由a1a2……aN这N个字符组成,Len(A)=N
B=b1b2……bM,表示B是由b1b2……bM这M个字符组成,Len(B)=M
定义LCS(i,j)=LCS(a1a2……ai,b1b2……bj),其中0≤i≤N,0≤j≤M
故: LCS(N,M)=LCS(A,B)
LCS(0,0)=0
LCS(0,j)=0
LCS(i,0)=0
对于1≤i≤N,1≤j≤M,有公式一
若ai=bj,则LCS(i,j)=LCS(i-1,j-1)+1
若ai≠bj,则LCS(i,j)=Max(LCS(i-1,j-1),LCS(i-1,j),LCS(i,j-1))
计算LCS(A,B)的算法有很多,下面介绍的Needleman/Wunsch算法是其中的一种。和LD算法类似,Needleman/Wunsch算法用的都是动态规划的思想。在Needleman/Wunsch算法中还设定了一个权值,用以区分三种操作(插入、删除、更改)的优先级。在下面的算法中,认为三种操作的优先级都一样。故权值默认为1。
举例说明:A=GGATCGA,B=GAATTCAGTTA,计算LCS(A,B)
第一步:初始化LCS矩阵
Needleman/Wunsch算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
G
0 |
|
|
|
|
|
|
|
|
|
|
|
G
0 |
|
|
|
|
|
|
|
|
|
|
|
A
0 |
|
|
|
|
|
|
|
|
|
|
|
T
0 |
|
|
|
|
|
|
|
|
|
|
|
C
0 |
|
|
|
|
|
|
|
|
|
|
|
G
0 |
|
|
|
|
|
|
|
|
|
|
|
A
0 |
|
|
|
|
|
|
|
|
|
|
|
第二步:利用公式一,计算矩阵的第一行
Needleman/Wunsch算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
G
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
G
0 |
|
|
|
|
|
|
|
|
|
|
|
A
0 |
|
|
|
|
|
|
|
|
|
|
|
T
0 |
|
|
|
|
|
|
|
|
|
|
|
C
0 |
|
|
|
|
|
|
|
|
|
|
|
G
0 |
|
|
|
|
|
|
|
|
|
|
|
A
0 |
|
|
|
|
|
|
|
|
|
|
|
第三步:利用公式一,计算矩阵的其余各行
Needleman/Wunsch算法矩阵
G
A
A
T
T
C
A
G
T
T
A
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
G
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
G
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
A
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
T
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
C
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
G
0 |
1 |
2 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
A
0 |
1 |
2 |
3 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
6 |
则,LCS(A,B)=LCS(7,11)=6
可以看出,Needleman/Wunsch算法实际上和LD算法是非常接近的。故他们的时间复杂度和空间复杂度也一样。时间复杂度为O(MN),空间复杂度为O(MN)。空间复杂度经过优化,可以优化到O(M)。
LCS算法的代码如下:
#include <iostream>
using namespace std;
void swp(string &str1, string &str2)
{
string tmp = str1;
str1 = str2;
str2 = str1;
}
string lcs(string &str1, string &str2)
{
if(str1.size() > str2.size())
{
swp(str1, str2);
}
int min_size = str1.size();
int *lcs_arr = new int[min_size+1];
for(int i = 0; i <= min_size; i++)
{
lcs_arr[i] = 0;
}
int str1_len = str1.size();
int str2_len = str2.size();
int lcs_max = 0;
int pointer = 0;
for(int i = 0; i< str2_len;i++)
{
for(int j = str1_len -1 ;j>=0; j--)
{
if(str1[j] == str2[i])
{
lcs_arr[j+1] = lcs_arr[j] + 1;
}
else
{
lcs_arr[j+1] = 0;
}
if(lcs_arr[j+1] > lcs_max)
{
lcs_max = lcs_arr[j+1];
pointer = j;
}
}
}
delete [] lcs_arr;
string tmp ;
for(int k = pointer - lcs_max;k <= pointer; k++)
{
tmp += str1[k];
}
return tmp;
}
int main()
{
string a ;
string b ;
cout<<"please input 2 lcs string"<<endl;
cout<<"please input a"<<endl;
cin>>a;
cout<<"please input b"<<endl;
cin>>b;
cout<<"lcs is "<<lcs(a,b)<<endl;;
return 0;
}
分享到:
相关推荐
c源码编写的求两个字符串的最长公共子串,采用递归算法
原理 举例说明:A=GGATCGA,B=GAATTCAGTTA 第一步:初始化LD矩阵 公式一 若ai=bj,则LD(i,j)=LD(i-1,j-1) 若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 第二步:利用上述的公式一,计算第一行 ...
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x ...
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
一、问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子...在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。 二、求解算法 对于母串X=<x1,x2,⋯,xm
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 下面的算法是根据网上的java算法由酒逍遥 ...
最长公共子串(LCS)问题是一直使用的经典计算问题。 该项目探索 LCS,它的一个特例,最长回文子串 (LPS) 问题,以及它的概括以及不同的问题域如何影响算法性能。 我对这些问题实施了各种解决方案,讨论了它们的理论...
最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。...本资源编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
使用动态规划的两种方式实现的LCS(最大公共串)(下面的算法都会使用动态规划的两种方式来实现) 加权有向无环图中最短路径和最长路径 背包问题 最长回文子串(lps) ###幂乘:算法复杂度是O(lgn) ##贪心算法 活动...
协议特征识别技术中用到了一种重要的LCS算法,它是一种字符串比对算法,提取出字符串中的最长连续公共子串。然而,通过理论分析和实验表明:这个查找过程是一个时间复杂度较高的运算过程,如果输入的数据分组比较大...
也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别: 子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的
高级java笔试题 个人博客 c++ c++primer - c++primer顺序容器与关联容器的一些用法 effective c++ - effective c++笔记归纳 ...数据结构与一些算法,来自算法导论,数据结构与算法分析-...LCS(最长公共子串),Rabin-Karp,
leetcode 2 算法 总结leetcode刷题的常见算法 常见的排序算法 二分查找 陷阱雨水 跳跃游戏 - II 机器人行走 堆栈实现 计算器(整数) ...LCS(最长公共子串) LD(莱文斯坦距离) DATrie(未完成)
在 O(n log n) 时间空间预处理后(或较复杂的 O(n) 时间空间 预处理), 可以 O(1) 回答: 两个子串的最长公共前缀 (LCP)、最 长公共后缀 (LCS)。 对于拥有周期 p 的串 s, LCP(s[1..n], s[1 + p..n]) = n − p。 输入 ...