ホームページ > 記事 > ウェブフロントエンド > JavaScript で最大共通部分文字列を見つける方法の詳細な説明
JavaScript で最大共通部分文字列を見つける方法の詳細な説明
- 小云云オリジナル
- 2018-02-05 09:44:031715ブラウズ
この記事では主に、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 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
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 があり、それらの共通部分文字列は <= Math.min(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='text/css'>
body {background-color:#fff;}
</style>
</head>
<body>
<script type='text/javascript'>
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 までご連絡ください。