Maison > Article > interface Web > Explication détaillée de la façon de trouver la plus grande sous-chaîne commune en JavaScript

Explication détaillée de la façon de trouver la plus grande sous-chaîne commune en JavaScript

小云云original: 2018-02-05 09:44:031757parcourir

Cet article vous 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 associées de JavaScript pour les chaînes. Les amis qui en ont besoin pourront s'y référer. .

Pour trouver la plus grande sous-chaîne commune, une approche 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.

	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

Compare chaque élément des deux chaînes S'ils correspondent, l'élément est 1, sinon, il 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 ?

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é.

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 pas réellement optimal, pourquoi ? Parce que la méthode d'écriture ci-dessus doit attendre que les deux niveaux de boucles soient terminés. 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>

Recommandations associées :

Explication détaillée de l'utilisation de PHP pour trouver le fil conducteur le plus long entre deux chaînes Sous-chaîne

Implémentation PHP de l'idée de trouver la sous-chaîne commune la plus longue

Résumé des points à noter concernant sous-chaînes communes

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration：

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Article précédent：Explication détaillée des exemples de modèles de médiateur JavaScriptArticle suivant：Explication détaillée des exemples de modèles de médiateur JavaScript

Articles Liés

Voir plus