本文共 3571 字,大约阅读时间需要 11 分钟。
求最大公共子串,常见的做法是使用矩阵。假设有字符串: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" "" > |
002 | <html xmlns= "" > |
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://gozqi.baihongyu.com/