string-matching - javascript 文字列 検索 - JavaScriptで文字列に部分文字列が含まれているかどうかを調べるには?

substringとは / javascript / string / substring

通常、 String.contains() メソッドを期待しますが、そうではないようです。

29 revs, 19 users 18%



Answer #1

これは、https://www.nayuki.io/res/knuth-morris-pratt-string-matching/kmp-string-matcher.jsから取得したProjectNayukiによるJavaScriptの実装です。

// Knuth-Morris-Pratt文字列照合アルゴリズムを使用して、指定されたテキスト文字列内の指定されたパターン文字列を検索します。
//パターンが見つかった場合、これは「text」で最も早い一致の開始のインデックスを返します。それ以外の場合は-1が返されます。
function kmpSearch(pattern, text) {
  if (pattern.length == 0)
    return 0; //即時一致

  //最長のサフィックス-プレフィックステーブルを計算します
  var lsp = [0]; // 規範事例
  for (var i = 1; i < pattern.length; i++) {
    var j = lsp[i - 1]; //前のLSPを拡張していると仮定することから始めます
    while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
      j = lsp[j - 1];
    if (pattern.charAt(i) == pattern.charAt(j))
      j++;
    lsp.push(j);
  }

  //テキスト文字列をウォークスルー
  var j = 0; //パターンで一致した文字の数
  for (var i = 0; i < text.length; i++) {
    while (j > 0 && text.charAt(i) != pattern.charAt(j))
      j = lsp[j - 1]; //パターンにフォールバックします
    if (text.charAt(i) == pattern.charAt(j)) {
      j++; //次の文字が一致し、位置をインクリメントします
      if (j == pattern.length)
        return i - (j - 1);
    }
  }
  return -1; // 見つかりません
}

console.log(kmpSearch('ays', 'haystack') != -1) // true
console.log(kmpSearch('asdf', 'haystack') != -1) // false