JavaScript で最大の共通部分文字列を見つける方法-jsチュートリアル-php.cn

ホームページ

ウェブフロントエンド

jsチュートリアル

JavaScript で最大の共通部分文字列を見つける方法

Jun 08, 2018 am 10:37 AM

javascript

この記事では主に、JavaScript で最大共通部分文字列を実現する方法を紹介します。これには、JavaScript のトラバーサル、マッチング、操作、その他の文字列の関連操作スキルが含まれます。必要な方は参考にしてください。

この記事の例では、 JavaScript 部分文字列メソッドの最大共通部分文字列。参考のために皆さんと共有してください。詳細は次のとおりです:

最大の共通部分文字列を見つけるには、一般的な方法は行列を使用することです。文字列 abcdefg と文字列 abcd があると仮定すると、次の表に示すように行列を形成できます。

はい、戦略を変更する必要があります。項目が一致する場合、項目の値は再び 1 に設定されますが、その対角線は a[i-1, j-1](i > 1 && j > ; 1) の値は +1 であるため、1 次元配列のみを使用できます。 2つの文字列の各項目を比較し、一致する場合は1、一致しない場合は0となります。次に、最も長い対角線が 1 であるシーケンス、つまり最大の共通部分文字列を見つけます。上記の分離を見ると、両方の文字列が大きい場合、2 次元配列を使用する必要があるように見えますが、さらに最適化することはできますか?

一方の文字列を「行」、もう一方の文字列を「列」として使用し、2つの文字列の各項目の値を比較し、別の変数を使用して配列の最大値とその開始位置を記録します。弦。コードは次のとおりです:

function LCS(str1, str2) {
 if (str1 === &quot;&quot; || str2 === &quot;&quot;) {
  return &quot;&quot;;
 }
 var len1 = str1.length;
 var len2 = str2.length;
 var a = new Array(len1);
 var maxLen = 0;
 var maxPos = 0;
 for (var i = 0; i &lt; len1; i++) { //行
  for (var j = len2 - 1; j &gt;= 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] &gt; maxLen) {
    maxLen = a[j];
    maxPos = j;
   }
  }
 }
 return str1.substr(maxPos - maxLen + 1, maxLen);
}

ログイン後にコピー

しかし、コードは実際には最適ではありません。なぜでしょうか?なぜなら、上記の書き込み方法では、ループの両方の層が完了するまで待機する必要があるからです。比較的高速な方法はありますか?

長さがそれぞれ len1 と len2 である文字列 a と b があり、それらの共通部分文字列は <= Math.min(len1, len2) でなければならず、部分文字列は連続していて、部分文字列 a と b に属している必要があります。

function findMaxSubStr(s1,s2){
 var str= &quot;&quot;,
  L1=s1.length,
  L2=s2.length;
 if (L1&gt;L2){
  var s3=s1;
  s1=s2;
  s2=s3;
  s3 = null;
  L1=s2.length;
  L2 = s1.length;
 }
 for (var i=L1; i &gt; 0; i--) {
  for (var j= 0; j &lt;= L2 - i &amp;&amp; j &lt; L1; j++){
   str = s1.substr(j, i);
   if (s2.indexOf(str) &gt;= 0) {
    return str;
   }
  }
 }
 return &quot;&quot;;
}

ログイン後にコピー

まず s1 と s2 の長さを比較し、短い方の文字列を取得します。 substr(idex, len) したがって、短い文字列とその部分文字列を取り出し、それが長い文字列に存在するかどうかを判断し、存在する場合はそれを直接返し、存在しない場合は次の数字を削除します。

完全な例:

&lt;!DOCTYPE html PUBLIC &quot;-//W3C//DTD XHTML 1.0 Transitional//EN&quot; &quot;http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd&quot;&gt;
&lt;html xmlns=&quot;http://www.w3.org/1999/xhtml&quot;&gt;
 &lt;head&gt;
 &lt;title&gt;www.jb51.net&lt;/title&gt;
 &lt;style type=&#39;text/css&#39;&gt;
 body {background-color:#fff;}
 &lt;/style&gt;
 &lt;/head&gt;
 &lt;body&gt;
&lt;script type=&#39;text/javascript&#39;&gt;
function LCS(str1, str2) {
 if (str1 === &quot;&quot; || str2 === &quot;&quot;) {
 return &quot;&quot;;
 }
 var len1 = str1.length;
 var len2 = str2.length;
 var a = new Array(len1);
 var maxLen = 0;
 var maxPos = 0;
 for (var i = 0; i &lt; len1; i++) { //行
 for (var j = len2 - 1; j &gt;= 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] &gt; maxLen) {
 maxLen = a[j];
 maxPos = j;
 }
 }
 }
 return str1.substr(maxPos - maxLen + 1, maxLen);
}
function findMaxSubStr(s1,s2){
 var str= &quot;&quot;,
 L1=s1.length,
 L2=s2.length;
 if (L1&gt;L2) {
 var s3=s1;
 s1=s2;
 s2=s3;
 s3 = null;
 L1=s2.length;
 L2 = s1.length;
 }
 for (var i=L1; i &gt; 0; i--) {
 for (var j= 0; j &lt;= L2 - i &amp;&amp; j &lt; L1; j++){
   str = s1.substr(j, i);
   if (s2.indexOf(str) &gt;= 0) {
 return str;
  }
  }
 }
 return &quot;&quot;;
}
 !(function() {
 var tmpArr = [];
 for (var i = 97; i &lt; 97 + 26; i++) {
 tmpArr.push(String.fromCharCode(i));
 }
 var s2 = tmpArr.join(&quot;&quot;);
 tmpArr.sort(function() {return Math.random() &gt; 0.7;});
 var s1 = new Array(600).join(tmpArr.join(&quot;&quot;));
 var date = getNow();
 alert( &quot;消耗时间：&quot; + (getNow() - date) + &quot;秒 &quot; + LCS(s1, s2));
 date = getNow();
 alert( &quot;消耗时间：&quot; + (getNow() - date) + &quot;秒 &quot; + findMaxSubStr(s1, s2) );
 })();
function getNow() {
 return new Date().getTime();
}
&lt;/script&gt;
 &lt;/body&gt;
&lt;/html&gt;

ログイン後にコピー

上記は私が皆さんのためにまとめたものであり、将来皆さんのお役に立てば幸いです。

vue.jsでNginxを使用してクロスドメインの問題を解決する

vue+webpackで非同期コンポーネントの読み込みを実装する方法?

以上がJavaScript で最大の共通部分文字列を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。