suchen

Heim >Web-Frontend >js-Tutorial >Ausführliche Erklärung, wie man den größten gemeinsamen Teilstring in JavaScript findet

Ausführliche Erklärung, wie man den größten gemeinsamen Teilstring in JavaScript findet

小云云
小云云Original
2018-02-05 09:44:031774Durchsuche

Dieser Artikel stellt Ihnen hauptsächlich die Methode zum Finden des größten gemeinsamen Teilstrings in JavaScript vor, einschließlich der JavaScript-Traversal-, Matching-, Operations- und anderen verwandten Operationsfähigkeiten für Strings. Ich hoffe, er kann Ihnen helfen .

Um den größten gemeinsamen Teilstring zu finden, ist ein gängiger Ansatz die Verwendung einer Matrix. Unter der Annahme, dass es Zeichenfolgen gibt: abcdefg und Zeichenfolge abcd, kann eine Matrix wie in der folgenden Tabelle dargestellt gebildet werden.


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

Vergleicht jedes Element der beiden Zeichenfolgen. Wenn sie übereinstimmen, ist das Element 1, wenn nicht, ist es 0. Finden Sie dann die Sequenz mit der längsten Diagonale von 1, die der größte gemeinsame Teilstring ist. Wenn man sich die obige Trennung ansieht, scheint es, dass wir ein zweidimensionales Array verwenden müssen. Dies ist nicht sehr kostengünstig, wenn beide Zeichenfolgen groß sind. Kann es weiter optimiert werden?

Ja, Sie müssen die Strategie ändern. Wenn das Element übereinstimmt, wird der Wert des Elements wieder auf 1 gesetzt, aber seine Diagonale a[i-1, j-1](i > ; 1 && j > 1) Der Wert +1, sodass nur ein eindimensionales Array verwendet werden kann.

Verwenden Sie eine Zeichenfolge als „Zeile“ und die andere als „Spalte“, vergleichen Sie die Werte jedes Elements der beiden Zeichenfolgen und verwenden Sie eine andere Variable, um den Maximalwert des Arrays und des Arrays aufzuzeichnen Startposition der Zeichenfolge. Der Code lautet wie folgt: 


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

Aber der Code ist eigentlich nicht optimal, warum? Weil die obige Schreibmethode warten muss, bis beide Schleifenebenen abgeschlossen sind. Gibt es eine relativ schnellere Methode?

Angenommen, die Zeichenfolgen a und b haben die Länge len1 bzw. len2. Ihre gemeinsame Teilzeichenfolge muss <= Math.min(len1, len2) sein, und die Teilzeichenfolge muss kontinuierlich sein und Teilzeichenfolgen von a und sein 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 "";
}

Vergleichen Sie zuerst die Längen von s1 und s2 und nehmen Sie dann die kürzere Zeichenfolge. substr(idex, len) Nehmen Sie also die kürzere Zeichenfolge und deren Teilzeichenfolge und ermitteln Sie dann, ob sie in der längeren Zeichenfolge vorhanden ist. Wenn sie vorhanden ist, geben Sie sie direkt zurück, andernfalls entfernen Sie die nächste Ziffer.

Vollständiges Beispiel: 


<!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>

Verwandte Empfehlungen:

Detaillierte Erläuterung der Verwendung von PHP zum Finden des längsten gemeinsamen Threads zwischen zwei Zeichenfolgen Teilzeichenfolge

PHP-Implementierung der Idee, die längste gemeinsame Teilzeichenfolge zu finden

Zusammenfassung der zu beachtenden Punkte zu gemeinsamen Teilzeichenfolgen

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung, wie man den größten gemeinsamen Teilstring in JavaScript findet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme：
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel：Ausführliche Erläuterung der Beispiele für JavaScript-MediatormusterNächster Artikel：Ausführliche Erläuterung der Beispiele für JavaScript-Mediatormuster

In Verbindung stehende Artikel

Mehr sehen