Может быть время, когда вы ищете такую функциональность, как String.Contains(). Ну, в JavaScript такой функции нет. Следовательно, каким будет лучший способ добиться этого?
EcmaScript-6
Если вы используете самую последнюю версию JavaScript, для разработки вы можете использовать функцию includes в прототипе строки.
ECMAScript 6 представил String.prototype.includes
const string = "foo";
const substring = "oo";
console.log(string.includes(substring)); // true
include выполняет с учетом регистра поиск в строке.
Как разработчики, вы должны быть бдительны, когда используются включения. Старые браузеры, особенно Internet Explorer, не поддерживают String.prototype.includes. Это означает, что в вашем коде должен быть резервный механизм для обработки этих сред.
EcmaScript-5
indexOf можно использовать, чтобы решить, содержит ли строка подстроку или нет. Метод indexOf вернет -1, если подстрока отсутствует в строке. Он часто используется в массивах, и то же самое можно применить к строкам.
var string = "foo";
var substring = "oo";
console.log(string.indexOf(substring) !== -1); // true
indexOf выполняет с учетом регистра поиск в строке.
Сложность времени
Используете ли вы include или indexOf — оба наивных алгоритма требуют временной сложности O(m * n), где m — длина родительской строки, а n — длина подстроки.
Если вы стремитесь к решению, требующему меньшей временной сложности, вам нужно использовать другой алгоритм.
Алгоритм Кнута-Морриса-Пратта, также известный как KMP-алгоритм
Во-первых, KMP-алгоритм требует временной сложности O(m+n). Это намного быстрее и лучше, чем наивные.
Алгоритм KMP использует линейный подход для проверки наличия подстроки в строке или нет. Вот моя версия KMP-алгоритма.
function kmpSearch(pattern, text) { if (pattern.length == 0) return 0; // Immediate match var j = 0; // Number of chars matched in pattern for (var i = 0; i < text.length; i++) { if (text.charAt(i) != pattern.charAt(j)){ j = 0; // 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 }
То, что мы делаем выше, довольно просто. Давайте расшифруем поток, шаг за шагом:
- Если шаблон представляет собой пустую строку, вы можете вернуть true, потому что.
- Итерация по строке, символ за символом
- Если текущий символ в тексте не равен текущему символу в шаблоне, сбросить указатель шаблона на нулевой индекс
- Продолжайте повторять текст
- Если текущий символ в тексте равен текущему символу в шаблоне, увеличить позицию текущего символа в шаблоне
- Если длина указателя шаблона совпадает с длиной шаблона, вернуть начальный индекс шаблона в тексте
- Если шаблон так и не найден, вернуть -1
Алгоритм KMP определенно подойдет вам, если вы ищете линейный алгоритм для проверки наличия подстроки в тексте или нет.
Вывод
Теперь мы стали мастерами в том, как проверить, присутствует ли подстрока в строке или нет. Итак, пока это единственные три общепринятых и наиболее часто используемых метода проверки наличия шаблона в строке. Конечно, KMP-алгоритм не ограничивается JavaScript. Его можно реализовать на любом языке программирования. И это ваш линейный алгоритм проверки шаблонов в строке.
Если вам нравятся мои слова, подписывайтесь и продолжайте учиться.
Дополнительные материалы на plainenglish.io