Usually I would expect a String.contains()
method, but there doesn't seem to be one.
What is a reasonable way to check for this?
This question is related to
javascript
string
substring
string-matching
There is a String.prototype.includes
in ES6:
"potato".includes("to");
> true
Note that this does not work in Internet Explorer or some other old browsers with no or incomplete ES6 support. To make it work in old browsers, you may wish to use a transpiler like Babel, a shim library like es6-shim, or this polyfill from MDN:
if (!String.prototype.includes) {
String.prototype.includes = function(search, start) {
'use strict';
if (typeof start !== 'number') {
start = 0;
}
if (start + search.length > this.length) {
return false;
} else {
return this.indexOf(search, start) !== -1;
}
};
}
Another alternative is KMP (Knuth–Morris–Pratt).
The KMP algorithm searches for a length-m substring in a length-n string in worst-case O(n+m) time, compared to a worst-case of O(n·m) for the naive algorithm, so using KMP may be reasonable if you care about worst-case time complexity.
Here's a JavaScript implementation by Project Nayuki, taken from https://www.nayuki.io/res/knuth-morris-pratt-string-matching/kmp-string-matcher.js:
// 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) {_x000D_
if (pattern.length == 0)_x000D_
return 0; // Immediate match_x000D_
_x000D_
// Compute longest suffix-prefix table_x000D_
var lsp = [0]; // Base case_x000D_
for (var i = 1; i < pattern.length; i++) {_x000D_
var j = lsp[i - 1]; // Start by assuming we're extending the previous LSP_x000D_
while (j > 0 && pattern.charAt(i) != pattern.charAt(j))_x000D_
j = lsp[j - 1];_x000D_
if (pattern.charAt(i) == pattern.charAt(j))_x000D_
j++;_x000D_
lsp.push(j);_x000D_
}_x000D_
_x000D_
// Walk through text string_x000D_
var j = 0; // Number of chars matched in pattern_x000D_
for (var i = 0; i < text.length; i++) {_x000D_
while (j > 0 && text.charAt(i) != pattern.charAt(j))_x000D_
j = lsp[j - 1]; // Fall back in the pattern_x000D_
if (text.charAt(i) == pattern.charAt(j)) {_x000D_
j++; // Next char matched, increment position_x000D_
if (j == pattern.length)_x000D_
return i - (j - 1);_x000D_
}_x000D_
}_x000D_
return -1; // Not found_x000D_
}_x000D_
_x000D_
console.log(kmpSearch('ays', 'haystack') != -1) // true_x000D_
console.log(kmpSearch('asdf', 'haystack') != -1) // false
_x000D_
Source: Stackoverflow.com