Maison >interface Web >js tutoriel >Comment trouver la plus grande sous-chaîne commune en JavaScript

Comment trouver la plus grande sous-chaîne commune en JavaScript

亚连original: 2018-06-08 10:37:022276parcourir

Cet article présente principalement la méthode permettant de trouver la plus grande sous-chaîne commune en JavaScript, impliquant les compétences de traversée, de correspondance, d'opération et d'autres opérations connexes de JavaScript pour les chaînes. Les amis dans le besoin peuvent se référer à ce qui suit

Les exemples dans. cet article décrit la méthode de recherche de la plus grande sous-chaîne commune en JavaScript. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Pour trouver la plus grande sous-chaîne commune, une méthode courante consiste à utiliser une matrice. En supposant qu'il existe des chaînes : abcdefg et string abcd, une matrice peut être formée comme indiqué dans le tableau suivant.

Oui, vous devez changer de stratégie. Si l'élément correspond, la valeur de l'élément est à nouveau remise à 1, mais sa diagonale a[i-1, j-1](i > ; 1 && j > 1) La valeur +1, afin que seul un tableau unidimensionnel puisse être utilisé. Chaque élément des deux chaînes est comparé, et s'il correspond, c'est 1, s'il ne correspond pas, c'est 0. Trouvez ensuite la séquence avec la plus longue diagonale de 1, qui est la plus grande sous-chaîne commune. En regardant la séparation ci-dessus, il semble que nous devions utiliser un tableau bidimensionnel. Cela n'est pas très rentable lorsque les deux chaînes sont grandes. Peut-il être optimisé davantage ?

Utilisez une chaîne comme "ligne" et l'autre comme "colonne", comparez les valeurs de chaque élément des deux chaînes et utilisez une autre variable pour enregistrer la valeur maximale du tableau et la position de départ de la chaîne. Le code est le suivant :

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

Mais le code n'est effectivement pas optimal, pourquoi ? Parce que la méthode d'écriture ci-dessus doit attendre que les deux couches de boucles soient terminées. Existe-t-il une méthode relativement plus rapide ?

Supposons que les chaînes a et b, dont les longueurs sont respectivement len1 et len2, leur sous-chaîne commune doivent être <= Math.min(len1, len2), et la sous-chaîne doit être continue et doit être des sous-chaînes de a et. 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 "";
}

Comparez d'abord les longueurs de s1 et s2, puis prenez la ficelle la plus courte. substr(idex, len), prenez donc la chaîne la plus courte et prenez sa sous-chaîne, puis déterminez si elle existe dans la chaîne la plus longue. Si elle existe, renvoyez-la directement, sinon supprimez le chiffre suivant.

Exemple complet :

<!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=&#39;text/css&#39;>
 body {background-color:#fff;}
 </style>
 </head>
 <body>
<script type=&#39;text/javascript&#39;>
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>

Ce qui précède est ce que j'ai compilé pour vous. J'espère que cela vous sera utile à l'avenir.

Articles Liés

Voir plus