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

ホームページ

ウェブフロントエンド

jsチュートリアル

JavaScript で最大共通部分文字列を見つける方法の詳細な説明

小云云

Feb 05, 2018 am 09:44 AM

javascriptjs方法

この記事では主に、JavaScript のトラバーサル、マッチング、操作、およびその他の関連する文字列の操作スキルを含む、JavaScript で最大の共通部分文字列を見つける方法を紹介します。

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

両方の文字列の各項目の d0001000

	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

項目が 1 の場合一致する場合は 0、一致しない場合は 0。次に、最も長い対角線が 1 であるシーケンス、つまり最大の共通部分文字列を見つけます。上記の分離を見ると、両方の文字列が大きい場合、2 次元配列を使用する必要があるように見えますが、さらに最適化することはできますか?

はい、戦略を変更する必要があります。項目が一致する場合、項目の値は再び 1 に設定されますが、その対角線は

a[i-1, j-1](i > 1 && j > ; 1) の値は +1 であるため、1 次元配列のみを使用できます。

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

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

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

長さがそれぞれ len1 と len2 である文字列 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 "";
}

まず s1 と s2 の長さを比較し、短い方の文字列を取得します。

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

完全な例:

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

関連する推奨事項:

PHP を使用して 2 つの文字列の最長の共通部分文字列を見つける方法の詳細な説明

PHP は、最長の共通部分文字列を見つけるというアイデアを実装します

パブリック部分文字列に関する注意事項のまとめ

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

声明

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

JavaScriptエンジンの理解：実装の詳細Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1）エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2）実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3）ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

Python vs. JavaScript：学習曲線と使いやすさApr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

Python vs. JavaScript：コミュニティ、ライブラリ、リソースApr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1）Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2）Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3）どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

C/CからJavaScriptへ：すべてがどのように機能するかApr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1）C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2）C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3）JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptエンジン：実装の比較Apr 13, 2025 am 12:05 AM

さまざまなJavaScriptエンジンは、各エンジンの実装原則と最適化戦略が異なるため、JavaScriptコードを解析および実行するときに異なる効果をもたらします。 1。語彙分析：ソースコードを語彙ユニットに変換します。 2。文法分析：抽象的な構文ツリーを生成します。 3。最適化とコンパイル：JITコンパイラを介してマシンコードを生成します。 4。実行：マシンコードを実行します。 V8エンジンはインスタントコンピレーションと非表示クラスを通じて最適化され、Spidermonkeyはタイプ推論システムを使用して、同じコードで異なるパフォーマンスパフォーマンスをもたらします。

ブラウザを超えて：現実世界のJavaScriptApr 12, 2025 am 12:06 AM

現実世界におけるJavaScriptのアプリケーションには、サーバー側のプログラミング、モバイルアプリケーション開発、モノのインターネット制御が含まれます。 2。モバイルアプリケーションの開発は、ReactNativeを通じて実行され、クロスプラットフォームの展開をサポートします。 3.ハードウェアの相互作用に適したJohnny-Fiveライブラリを介したIoTデバイス制御に使用されます。

next.jsを使用してマルチテナントSaaSアプリケーションを構築する（バックエンド統合）Apr 11, 2025 am 08:23 AM

私はあなたの日常的な技術ツールを使用して機能的なマルチテナントSaaSアプリケーション（EDTECHアプリ）を作成しましたが、あなたは同じことをすることができます。まず、マルチテナントSaaSアプリケーションとは何ですか？マルチテナントSaaSアプリケーションを使用すると、Singの複数の顧客にサービスを提供できます

next.jsを使用してマルチテナントSaaSアプリケーションを構築する方法（フロントエンド統合）Apr 11, 2025 am 08:22 AM

この記事では、許可によって保護されたバックエンドとのフロントエンド統合を示し、next.jsを使用して機能的なedtech SaaSアプリケーションを構築します。 FrontEndはユーザーのアクセス許可を取得してUIの可視性を制御し、APIリクエストがロールベースに付着することを保証します

See all articles

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SecLists

SecLists は、セキュリティテスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティテスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティテストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジングペイロード、機密データパターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテストマシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。

WebStorm Mac版

便利なJavaScript開発ツール

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、