Может быть время, когда вы ищете такую ​​функциональность, как 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
}

То, что мы делаем выше, довольно просто. Давайте расшифруем поток, шаг за шагом:

  1. Если шаблон представляет собой пустую строку, вы можете вернуть true, потому что.
  2. Итерация по строке, символ за символом
  3. Если текущий символ в тексте не равен текущему символу в шаблоне, сбросить указатель шаблона на нулевой индекс
  4. Продолжайте повторять текст
  5. Если текущий символ в тексте равен текущему символу в шаблоне, увеличить позицию текущего символа в шаблоне
  6. Если длина указателя шаблона совпадает с длиной шаблона, вернуть начальный индекс шаблона в тексте
  7. Если шаблон так и не найден, вернуть -1

Алгоритм KMP определенно подойдет вам, если вы ищете линейный алгоритм для проверки наличия подстроки в тексте или нет.

Вывод

Теперь мы стали мастерами в том, как проверить, присутствует ли подстрока в строке или нет. Итак, пока это единственные три общепринятых и наиболее часто используемых метода проверки наличия шаблона в строке. Конечно, KMP-алгоритм не ограничивается JavaScript. Его можно реализовать на любом языке программирования. И это ваш линейный алгоритм проверки шаблонов в строке.

Если вам нравятся мои слова, подписывайтесь и продолжайте учиться.

Дополнительные материалы на plainenglish.io