JavaScriptは最大の公共串を求める方法を実現します.

本論文の実例は、JavaScriptの実現において最大の共通部分列を求める方法を述べている.皆さんに参考にしてあげます.具体的には以下の通りです.
最大の公共のサブストリングを求めて、よくあるやり方は行列を使うのです.文字列:abcdefgと文字列abcdがあると仮定すると、次の表のような行列が構成されてもよい.
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
2つの文字列の各項目を比較します.一致する場合は1、不一致は0です.それから対角線の一番長いのが1のあの1段の序列なことを求めて、最大の公共のサブストリングです.上の分離を見ると、二次元配列が使われているようですが、二文字列が大きい場合はお得ではないです.もっと最適化できますか?
はい、ポリシーを変更する必要があります.これが一致すると、この項目の値はもう1に設定されます.その対角線a[i-1,j-1](i>1&j>1)の値＋1となり、1次元配列のみを使用することができます.
一つの文字列を「行」とし、もう一つは「列」として、二つの文字列の各値を比較し、もう一つの変数で配列の最大値と文字列の開始位置を記録します.コードは以下の通りです

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

コードは実は最適ではないです.なぜですか?上記の表記は二重の循環が完了するまで待たなければならないからです.もっと早い方法がありますか?
文字列a、bが設けられており、その長さはそれぞれlen 1、len 2であり、その共通文字列は必ず<=Math.min(len 1、len 2)であり、しかも子列は必ず連続し、かつa、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 "";
}

s 1、s 2の長さを先に比較し、短い文字列を取ってください.substr(idex, len)ですので、短い列を持ってサブストリングを取り、その後、長い文字列の中に存在するかどうかを判断します.中に入れば直接戻ります.そうでなければ、次の桁を取ります.
完全な例:

 
 
 
 
 

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

 

もっと多くのJavaScript関連の内容について興味がある読者は、当駅のテーマを見ることができます.「JavaScript数学演算の使い方のまとめ」、「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript配列操作技術のまとめ」、「JavaScript順序付けアルゴリズムのまとめ」、「JavaScriptアルゴリズムと技術のまとめ」「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます.