`
yihuijie2011
  • 浏览: 8833 次
社区版块
存档分类
最新评论

最大公共子串算法

阅读更多

     有两种思想,就像珠宝商放在天鹅绒上的宝石一样熠熠生辉。一个是微积分,另一个就是算法。微积分以及在微积分基础上建立起的数学分析体系造就了现代科学,而算法造就了现代世界。

                                                                                                          ——David Berlinski

最大公共子串问题JavaScript版

求最大公共子串,常见的做法是使用矩阵。假设有字符串:abcdefg和字符串abcd,则可构成如下矩阵。

1     a    b    c    d    e    f    g
2 a   1    0    0    0    0    0    0
3 b   0    1    0    0    0    0    0
4 c   0    0    1    0    0    0    0
5 d   0    0    0    1    0    0    0

对两个字符串的每一项都进行比较,若匹配则该项为1,不匹配则为0。然后求出对角线最长为1的那一段序列,即为最大公共子串。看上面的分开,似乎得使用二维数组了,在两个字符串都较大的情况下不是很划算,是否可以进一步优化?

可以,需要改变一下策略,如果该项匹配,则该项的值为再设为1,而是其对角线a[i-1, j-1](i > 1 && j > 1)的值+1,这样便可以只使用一个一维数组。

以一个字符串作为“行”,另一个作为“列”,比较两个字符串各项的值,用另外一个变量记录数组的最大值和字符串的起始位置。代码如下:

01 function LCS(str1, str2) {
02   
03     if (str1 === "" || str2 === "") {
04         return "";
05     }
06   
07     var len1 = str1.length;
08     var len2 = str2.length;
09       
10     var a = new Array(len1);
11     var maxLen = 0;
12     var maxPos = 0;
13       
14     for (var i = 0; i < len1; i++) { //行
15         for (var j = len2 - 1; j >= 0; j--) {//列 
16             if (str1.charAt(j) == str2.charAt(i)) {
17                 if (i === 0 || j === 0) {
18                     a[j] = 1;
19                 } else {
20                     a[j] = a[j - 1] + 1;
21                 }
22             } else {
23                 a[j] = 0;
24             }
25   
26             if (a[j] > maxLen) {
27                 maxLen = a[j];
28                 maxPos = j;
29             }
30         }
31     }
32   
33     return str1.substr(maxPos - maxLen + 1, maxLen);
34 }

但代码其实并不是最优的,为什么?因为上面的写法必须等待两层循环都完成。有没有相对更快一些的方法呢?

设有字符串a、b,其长度分别为len1、len2,其公共字子串一定是 <= Math.min(len1, len2),而且子串必定连续,且一定是a、b的子串。

01 function findMaxSubStr(s1,s2){ 
02     var str= "",
03         L1=s1.length,
04         L2=s2.length; 
05       
06     if (L1>L2){ 
07         var s3=s1;
08         s1=s2;
09         s2=s3;
10         s3 = null;
11         L1=s2.length;
12         L2 = s1.length;
13     }
14       
15       
16     for (var i=L1; i > 0; i--) {
17         for (var j= 0; j <= L2 - i && j < L1; j++){ 
18             str = s1.substr(j, i);
19             if (s2.indexOf(str) >= 0) {
20                 return str; 
21             }
22         
23     }
24       
25     return ""
26 }

先比较s1、s2的长度,然后取较短的字符串作为。substr(idex, len),所以拿较短的串取其子串,然后判断它是否在较长的字符串中存在,如果存中则直接返回,否则再取下一位。

完整示例:

001 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
002 <html xmlns="http://www.w3.org/1999/xhtml">
003  <head>
004   <title>www.nowamagic.net</title>
005   <style type='text/css'>
006     body {background-color:#fff;}
007   </style>
008  </head>
009   
010  <body>
011 <script type='text/javascript'>
012 function LCS(str1, str2) {
013   
014     if (str1 === "" || str2 === "") {
015         return "";
016     }
017   
018     var len1 = str1.length;
019     var len2 = str2.length;
020       
021     var a = new Array(len1);
022     var maxLen = 0;
023     var maxPos = 0;
024       
025     for (var i = 0; i < len1; i++) { //行
026         for (var j = len2 - 1; j >= 0; j--) {//列 
027             if (str1.charAt(j) == str2.charAt(i)) {
028                 if (i === 0 || j === 0) {
029                     a[j] = 1;
030                 } else {
031                     a[j] = a[j - 1] + 1;
032                 }
033             } else {
034                 a[j] = 0;
035             }
036   
037             if (a[j] > maxLen) {
038                 maxLen = a[j];
039                 maxPos = j;
040             }
041         }
042     }
043   
044     return str1.substr(maxPos - maxLen + 1, maxLen);
045 }
046   
047   
048 function findMaxSubStr(s1,s2){ 
049     var str= "",
050     L1=s1.length,
051     L2=s2.length; 
052       
053     if (L1>L2) { 
054     var s3=s1;
055     s1=s2;
056     s2=s3;
057     s3 = null;
058     L1=s2.length;
059     L2 = s1.length;
060     }
061       
062       
063     for (var i=L1; i > 0; i--) {
064     for (var j= 0; j <= L2 - i && j < L1; j++){ 
065             str = s1.substr(j, i);
066             if (s2.indexOf(str) >= 0) {
067         return str; 
068         }
069        
070     }
071       
072     return ""
073
074   
075   
076     !(function() {
077     var tmpArr = [];
078     for (var i = 97; i < 97 + 26; i++) {
079         tmpArr.push(String.fromCharCode(i));
080     }
081       
082     var s2 = tmpArr.join("");
083   
084     tmpArr.sort(function() {return Math.random() > 0.7;});
085     var s1 = new Array(600).join(tmpArr.join(""));
086       
087       
088     var date = getNow();
089     alert(  "消耗时间:" + (getNow() - date) + "秒  " + LCS(s1, s2));
090   
091     date = getNow();
092     alert(  "消耗时间:" + (getNow() - date) + "秒  " + findMaxSubStr(s1, s2) );
093    })();
094   
095 function getNow() {
096     return new Date().getTime();
097 }
098 </script>
099  </body>
100 </html>

正文转载于http://www.nowamagic.net/algorithm/algorithm_LargestCommonSubstring.php

0
0
分享到:
评论
1 楼 暴风雪 2012-03-18  
膜拜效率是O(n^2)的算法……为什么不用后缀树/后缀数组优化到O(logn)呢?

相关推荐

    最大公共子串计算论文相似度源程序

    最大公共子串计算论文相似度:事件复杂度O(m*n),空间复杂度Omin(m,n)),可以用来计算两个字符串的最大公共子串长度、相似度;可以用于论文相似度量、地理信息等基于相似度量的查询等环境。由于空间复杂度低,因此可...

    动态规划实现两序列最大公共子串查找(Python代码)

    最大公共子串问题是IT行业的经典面试题之一,在生物信息等领域也有重要应用。该资源使用动态规划实现了最大公共子串查找算法,问题具体描述在Problem里,代码为code.py,调试结果请参考Readme。

    C++实现找出两个字符串中最大的公共子串

    本主题将深入探讨如何使用C++语言来实现一个算法,该算法能够找出两个字符串中的最大公共子串。公共子串是指同时存在于两个或多个字符串中的任意非空字符序列。在本问题中,我们目标是找到最长的这样一个子串。 ...

    LCS(longest common substring)算法,即最大公共子串 C实现

    LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...

    java实现字符串匹配求两个字符串的最大公共子串

    在Java编程中,实现字符串匹配并寻找两个字符串的最大公共子串是一项常见的任务,尤其是在文本处理、数据比较和信息检索等领域。本示例介绍了一种基于二维数组(也称为动态规划矩阵)的算法来解决这个问题。 最大...

    JavaScript实现求最大公共子串的方法

    标题中的"JavaScript实现求最大公共子串的方法"指的是在JavaScript编程语言中寻找两个字符串共有的最长子串。这个任务在计算机科学中属于字符串处理的一部分,常用于文本分析、比较和搜索算法。 描述中提到的...

    最长公共子串MFC实现

    最后,最长公共子串的长度就是dp数组的最大值,而子串本身可以通过回溯dp数组得到。 在MFC项目中,我们可以将这些算法逻辑封装到一个类中,比如CLCSAlgorithm,该类包含计算LCS的方法,并可能有一个成员变量来存储...

    最大公共资源子串

    本文将详细介绍如何利用C语言实现最大公共子串(Longest Common Substring,简称 LCS)的计算方法。最大公共子串问题是指在两个或多个字符串中找到最长的相同子串。本算法采用动态规划的方式解决这一问题,并通过一...

    新建 WinRAR 压缩文件_最长公共子串_

    在IT领域,尤其是在编程和算法设计中,"最长公共子串"是一个重要的概念。这个知识点主要涉及字符串处理和算法分析,对于计算机科学的学习者和开发者来说具有基础且实用的价值。在给定的压缩包文件中,我们可以看到它...

    获取最长公共子串

    在编程领域,"获取最长公共子串"是一个经典的问题,主要涉及到字符串处理和算法设计。这个问题的基本目标是从两个或多个给定的字符串中找到最长的共同连续子序列,即这个子序列是每个字符串的一部分,且在原字符串中...

    动态规划求最大匹配子串

    动态规划求最大匹配子串是计算机科学中的一种常见问题,旨在寻找两个字符串之间的最长公共子串。这种问题可以使用动态规划算法来解决,下面我们将详细介绍该算法的思想和实现。 算法思想: 假设我们有两个字符串...

    PHP实现求两个字符串最长公共子串的方法示例

    这样,数组$c$的每个元素就存储了对应位置的最大公共子串长度。 在循环结束后,我们遍历数组$c$找到最大值,并且找出对应的子串。我们使用`substr()`函数从字符串$b$中提取出最长公共子串,因为数组$c$是根据字符串...

    面试必考字符串相关的动态规划——最大公共子序列、最大公共子串、编辑距离

    字符串相关的动态规划最大公共子序列最大公共子串编辑距离 简述这三个算法解决的问题和展示状态转移方程并且给出可通过执行的Python代码。 最大公共子序列 子序列是,一个字符串中的任意字符组成的序列,重点在于,...

    动态规划:最长公共子串 LCS

    - 在 \( dp \) 数组中找到最大值及对应的位置,即可确定最长公共子串。 综上所述,动态规划方法和后缀树方法都是解决最长公共子串问题的有效手段。选择哪种方法取决于具体的应用场景以及对时间和空间复杂度的要求...

    python实现求两个字符串的最长公共子串方法

    在Python编程语言中,求解两个字符串的最长公共子串是一项常见的字符串处理任务。这个问题的解决方案通常基于动态规划思想,即将问题分解为更小的子问题,并存储子问题的解以便于后续使用,从而避免重复计算。下面...

    找两字符串中最大子串

    根据给定文件的信息,本文将详细介绍如何在两个字符串中寻找最大公共子串的算法实现。 ### 一、问题背景 在计算机科学中,查找两个字符串中的最大公共子串是一个非常实用的问题,它广泛应用于文本处理、生物信息学...

    《数据结构与算法》c语言实现代码

    总的来说,《数据结构与算法》C语言实现,尤其是“找两个字符串的最大公共子串”的代码,提供了对数据结构和算法实践经验的宝贵机会,有助于提升编程技能和问题解决能力。通过深入学习和实践这个案例,可以为未来在...

    算法系列之六:最长公共子序列(LCS)问题(连续子序列)的三种解法.doc

    如果两个字符串的首字符不相等,则用三种对齐策略分别计算可能的最长公共子串,然后取最长的一个与当前已知的最长公共子串比较,如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串...

    js判断出两个字符串最大子串的函数实现方法

    在本文中,我们探讨了如何使用JavaScript(js)编写一个函数来找出两个字符串中的最大公共子串。这涉及到字符串处理的知识,以及算法的实现,特别是动态规划和双指针技术。 首先,需要明确的是字符串的最大公共子串...

Global site tag (gtag.js) - Google Analytics