質問: javascriptで文字列に部分文字列が含まれているかどうかを確認する方法 通常私はstring.contains()メソッドを期待するでしょう、しかしそれがあるようには思われません。これを確認するための合理的な方法は何ですか?
回答: 他の選択肢は _ kmp _ です。kmpアルゴリズムは最悪の場合の線形時間部分文字列検索を提供するので、最悪の場合の時間の複雑さを気にするのであれば妥当な方法です。これは、project nayukiによる https://www.nayuki.io/res/knuth-morris-pratt-string-matching/kmp-string-matcher.js からのjavascript実装です。// searches for the given pattern string in the given text string using the knuth-morris-pratt string matching algorithm. // if the pattern is found, this returns the index of the start of the earliest match in 'text'. otherwise -1 is returned. function kmpsearch(pattern, text) { if (pattern.length == 0) return 0; // immediate match // compute longest suffix-prefix table var lsp = [0]; // base case for (var i = 1; i < pattern.length; i++) { var j = lsp[i - 1]; // start by assuming we're extending the previous 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); } // walk through text string var j = 0; // number of chars matched in pattern for (var i = 0; i < text.length; i++) { while (j > 0 && text.charat(i) != pattern.charat(j)) j = lsp[j - 1]; // fall back in the pattern if (text.charat(i) == pattern.charat(j)) { j++; // next char matched, increment position if (j == pattern.length) return i - (j - 1); } } return -1; // not found } 使用例kmpsearch('ays', 'haystack') != -1 // true kmpsearch('asdf', 'haystack') != -1 // false