JavaScript实现求最大公共子串的方法
本文实例讲述了javascript实现求最大公共子串的方法。分享给大家供大家参考，具体如下：
求最大公共子串，常见的做法是使用矩阵。假设有字符串：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 < len1; i++) { //行
for (var j = len2 - 1; j >= 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，其公共字子串一定是 <= math.min(len1, len2)，而且子串必定连续，且一定是a、b的子串。
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 <= l2 - i && j < l1; j++){
str = s1.substr(j, i);
if (s2.indexof(str) >= 0) {
return str;
}
}
}
return "";
}
先比较s1、s2的长度，然后取较短的字符串作为。substr(idex, len)，所以拿较短的串取其子串，然后判断它是否在较长的字符串中存在，如果存中则直接返回，否则再取下一位。
完整示例：
<!doctype html public "-//w3c//dtd xhtml 1.0 transitional//en" "http://www.w3.org/tr/xhtml1/dtd/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>www.jb51.net</title>
<style type='text/css'>
body {background-color:#fff;}
</style>
</head>
<body>
<script type='text/javascript'>
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 < len1; i++) { //行
for (var j = len2 - 1; j >= 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);
}
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 <= l2 - i && j < l1; j++){
str = s1.substr(j, i);
if (s2.indexof(str) >= 0) {
return str;
}
}
}
return "";
}
!(function() {
var tmparr = [];
for (var i = 97; i < 97 + 26; i++) {
tmparr.push(string.fromcharcode(i));
}
var s2 = tmparr.join("");
tmparr.sort(function() {return math.random() > 0.7;});
var s1 = new array(600).join(tmparr.join(""));
var date = getnow();
alert( "消耗时间：" + (getnow() - date) + "秒 " + lcs(s1, s2));
date = getnow();
alert( "消耗时间：" + (getnow() - date) + "秒 " + findmaxsubstr(s1, s2) );
})();
function getnow() {
return new date().gettime();
}
</script>
</body>
</html>
更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
下一篇： 正则表达式（轻松入门级）