suchen

Heim  >  Artikel  >  Web-Frontend  >  So finden Sie den größten gemeinsamen Teilstring in JavaScript

So finden Sie den größten gemeinsamen Teilstring in JavaScript

亚连
亚连Original
2018-06-08 10:37:022233Durchsuche

In diesem Artikel wird hauptsächlich die Methode zum Finden des größten gemeinsamen Teilstrings in JavaScript vorgestellt, einschließlich JavaScripts Durchlauf-, Matching-, Operations- und anderen verwandten Operationsfähigkeiten für Strings. Freunde in Not können sich auf die folgenden Beispiele beziehen Dieser Artikel beschreibt die Implementierung der Methode zum Finden der größten gemeinsamen Teilzeichenfolge in JavaScript. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Um den größten gemeinsamen Teilstring zu finden, ist eine übliche Methode die Verwendung einer Matrix. Unter der Annahme, dass es Zeichenfolgen gibt: abcdefg und Zeichenfolge abcd, kann eine Matrix wie in der folgenden Tabelle gezeigt gebildet 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. Jedes Element der beiden Zeichenfolgen wird verglichen. Wenn es übereinstimmt, ist es 1, wenn es nicht übereinstimmt, 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? 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.

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.

substr(idex, len)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>

Das Obige habe ich für alle zusammengestellt. Ich hoffe, dass es in Zukunft für alle hilfreich sein wird.

Verwandte Artikel:

Verwenden Sie Nginx in vue.js, um domänenübergreifende Probleme zu lösen

Verwenden Sie Nginx in vue.js, um zu lösen Domänenübergreifend

Wie implementiert man das asynchrone Laden von Komponenten in vue+webpack?

Das obige ist der detaillierte Inhalt vonSo finden Sie den größten gemeinsamen Teilstring in JavaScript. 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：So sortieren Sie SohndatenNächster Artikel：So sortieren Sie Sohndaten

In Verbindung stehende Artikel

Mehr sehen