yihuijie2011

浏览: 8537 次

最近访客更多访客>>

alonlys

z915139481

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

最大公共子串算法

博客分类：

算法

最大公共子串算法

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

——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>