溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》

JavaScript怎么實(shí)現(xiàn)求最大公共子串

發(fā)布時(shí)間：2021-04-13 11:24:48 來(lái)源：億速云 閱讀：286 作者：小新 欄目：web開(kāi)發(fā)

這篇文章將為大家詳細(xì)講解有關(guān)JavaScript怎么實(shí)現(xiàn)求最大公共子串，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

具體如下：

求最大公共子串，常見(jiàn)的做法是使用矩陣。假設(shè)有字符串：abcdefg和字符串a(chǎn)bcd，則可構(gòu)成如下表所示矩陣。


abcdefg
a1000000
b0100000
c0010000
d0001000

對(duì)兩個(gè)字符串的每一項(xiàng)都進(jìn)行比較，若匹配則該項(xiàng)為1，不匹配則為0。然后求出對(duì)角線(xiàn)最長(zhǎng)為1的那一段序列，即為最大公共子串?？瓷厦娴姆珠_(kāi)，似乎得使用二維數(shù)組了，在兩個(gè)字符串都較大的情況下不是很劃算，是否可以進(jìn)一步優(yōu)化？

可以，需要改變一下策略，如果該項(xiàng)匹配，則該項(xiàng)的值為再設(shè)為1，而是其對(duì)角線(xiàn)a[i-1, j-1](i > 1 && j > 1)的值+1，這樣便可以只使用一個(gè)一維數(shù)組。

以一個(gè)字符串作為“行”，另一個(gè)作為“列”，比較兩個(gè)字符串各項(xiàng)的值，用另外一個(gè)變量記錄數(shù)組的最大值和字符串的起始位置。代碼如下：

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);
}

但代碼其實(shí)并不是最優(yōu)的，為什么？因?yàn)樯厦娴膶?xiě)法必須等待兩層循環(huán)都完成。有沒(méi)有相對(duì)更快一些的方法呢？

設(shè)有字符串a(chǎn)、b，其長(zhǎng)度分別為len1、len2，其公共字子串一定是 <= Math.min(len1, len2)，而且子串必定連續(xù)，且一定是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的長(zhǎng)度，然后取較短的字符串作為。substr(idex, len)，所以拿較短的串取其子串，然后判斷它是否在較長(zhǎng)的字符串中存在，如果存中則直接返回，否則再取下一位。

完整示例：

<!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( "消耗時(shí)間：" + (getNow() - date) + "秒 " + LCS(s1, s2));
 date = getNow();
 alert( "消耗時(shí)間：" + (getNow() - date) + "秒 " + findMaxSubStr(s1, s2) );
 })();
function getNow() {
 return new Date().getTime();
}
</script>
 </body>
</html>

關(guān)于“JavaScript怎么實(shí)現(xiàn)求最大公共子串”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手