注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

[常用算法]最大公共子序列LCS  

2015-05-21 21:52:36|  分类: 常用算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定两个子序列,然后求解匹配他们最长的公共子序列。
首先我们想到就是暴力搜索的方法,这个就是没有技术含量了,而且时间上也是不允许的。其实,这个题用动态规划就能很好的解决。
假设两个串分别是s1和s2,他们我们可以给一个二维数组,表示lcs(i,j),这个用来表示当前是s1[i]是否等于s2[j]。举一个例子
s1 =  "acbd"   s2=“cb”
    a c b d
c | 0 1 0 0
b | 0 0 1 0 

仔细看看上面的矩阵,会发现,如果是匹配的子串的话,那么矩阵的那个位置的斜线方向肯定都是1。假设s1[i]和s2[j]那个位置是匹配字符串的最后一个字符,那么他们的上一个字符也肯定是匹配的,s1[i-1]==s2[j-1]。而如果用矩阵来表是当前匹配字符串的个数的话
if(s1[i]==s2[j])
lcs(i,j) = lcs(i-1,j-1)  +1;
otherwise
lcs(i,j) =0;
有了这个规律之后,我们来写一个最直观的程序

int LCS(char*s1,char*s2)
{
/*
*算法还可以改进,我们可以将查找最大长度和对应字符的工作放在构造矩阵的过程中完成,
*一边构造一边记录当前的最大长度和对应位置,这样就节省了n^2的查找时间。

*空间上也可以做改进,如果按照如上的方式构造,我们发现,当矩阵的第i+1行的值
*计算完成后,第i行的值就没有用了,即便是最长的长度出现在第i行,我们也已经用
*变量记录下来了。因此,可以将矩阵缩减成一个向量来处理,向量的当前值对应第i行,
*向量的下一个循环后的值对应第i+1行
*/
int len1 = strlen(s1);
int len2 = strlen(s2);
int** mark = (int**)malloc(len1*sizeof(int*));

int i, j;
for (i = 0; i < len1; i++)
{
mark[i] = (int*)malloc(len2*sizeof(int));
for (j = 0; j < len2; j++)
{
mark[i][j] = 0;
}
}
for (i = 0; i < len1; i++)
mark[i][0] = (s1[i] == s2[0]) ? 1 : 0;
for (j = 0; j < len2; j++)
mark[0][i] = (s1[0] == s2[j]) ? 1 : 0;

int max = 0;
int ps, pe = 0;
for (i = 1; i < len1; i++)
{
for (j = 1; j < len2; j++)
{
if (s1[i] == s2[j])
{
mark[i][j] = mark[i - 1][j - 1]+1;
}
else
{
mark[i][j] = 0;
}
if (mark[i][j] > max)
{
max = mark[i][j];
pe = i;
}
}
}

show(mark,len1,len2);
i = 0;
j = pe-max+1;
while (i < max)
{
cout << s1[j];
j++;
i++;
}
cout <<endl<< max << endl;
return max;
}

可以看到我们开了一个矩阵来存储当前匹配字符的个数,但是仔细分析的话,会发现,其实没有必要开一个二维数组。因为一旦i+1行计算完毕了,第i行根本就没有用了。所以可以节省空间,就有了

string LCS1(string s1, string s2)
{
int len1 = s1.size();
int len2 = s2.size();
vector<int>mark(len2+1,0);
int i, j;
for (i = 0; i < mark.size(); i++)
cout << mark[i]<<" ";
cout << endl;

int max = 0;
int ps, pe = 0;
for (i = 0; i < len1; i++)
{
for (j = len2; j > 0; j--)
{
if (s1[i] == s2[j - 1])
{
mark[j] = mark[j - 1] + 1;
}
else
{
mark[j] = 0;
}
if (mark[j] > max)
{
max = mark[j];
pe = i;
}
}
}
string result;
i = 0;
j = pe - max + 1;
result = s1.substr(j,max);
return result;
}

第二个循环必须从后往前更新,要不然 更新j+1位置的数时候用j位置的是该行的,而不是上一行的(相当于我们第一个程序里面矩阵的上一行)。

有几个参考,写的很不错,尤其是最后一个人的,里面还有其他的应用。

http://blog.csdn.net/steven30832/article/details/8260189
http://www.cnblogs.com/kuangbin/p/3309059.html
http://www.cnblogs.com/Lyush/archive/2013/08/25/3281546.html

 

  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017