php专区

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

    a    b    c    d    e    f    g
a   1    0    0    0    0    0    0
b   0    1    0    0    0    0    0
c   0    0    1    0    0    0    0
d   0    0    0    1    0    0    0

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

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

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

function LCS(str1, str2) {
    if (str1 === "" || str2 === "") {
        return "";
    }
    var len1 = str1.length;
    var len2 = str2.length;
    
    var a = new Array(len1);
    var maxLen = 0;
    var maxPos = 0;
    
    for (var i = 0; i = 0; j--) {//列 
            if (str1.charAt(j) == str2.charAt(i)) {
                if (i === 0 || j === 0) {
                    a[j] = 1;
                } else {
                    a[j] = a[j - 1] + 1;
                }
            } else {
                a[j] = 0;
            }
            if (a[j] > maxLen) {
                maxLen = a[j];
                maxPos = j;
            }
        }
    }
    return str1.substr(maxPos - maxLen + 1, maxLen);
}

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

设有字符串a、b，其长度分别为len1、len2，其公共字子串一定是

function findMaxSubStr(s1,s2){ 
    var str= "",
        L1=s1.length,
        L2=s2.length; 
    
    if (L1>L2){ 
        var s3=s1;
        s1=s2;
        s2=s3;
        s3 = null;
        L1=s2.length;
        L2 = s1.length;
    }
    
    
    for (var i=L1; i > 0; i--) {
        for (var j= 0; j = 0) {
                return str; 
            }
        } 
    }
    
    return ""; 
} 

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

完整示例：

本文地址：http://www.nowamagic.net/librarys/veda/detail/1596，欢迎访问原出处。