Алгоритмы поиска подстроки на JavaScript

Недавно я столкнулся с одной не очень сложной задачей на leetcode. В рамках задачи нужно было реализовать алгоритм поиска подстроки в строке. Пока я пытался сделать задачу, я понял, что я очень мало знаю про то как можно искать подстроку и решил изучить эту тему подробнее, и рассказать результат вам.

Как говорит Википедия “Поиск подстроки в строке — одна из простейших задач поиска информации”, но это не совсем так, ниже я расскажу про разные алгоритмы решения и покажу примеры их реализации. Начнем!

“Алгоритм грубой силы” или “Алгоритм простого поиска”

Алгоритм грубой силы - это простой алгоритм поиска подстроки, он заключается в последовательном переборе всех символов строки и проверки совпадения с искомой подстрокой. Если совпадение не найдено, то алгоритм сдвигает искомую подстроку на один символ вправо и начинает поиск снова.

const strStr = (haystack, needle) => {
  const m = needle.length
  const n = haystack.length

  for (let windowStart = 0; windowStart <= n - m; windowStart++) {
    for (let i = 0; i < m; i++) {
      if (needle[i] !== haystack[windowStart + i]) {
        break
      }
      if (i === m - 1) {
        return windowStart
      }
    }
  }

  return -1
}

Функция поиска состоит из цикла, который ограничивается до n - m (длина искомой строки - длина строки в которой ищем), что позволяет обойти проблему, если строка имеет меньше символов чем искомая строка и избежать лишних проверок. И вложенного цикла, который имеет в себе логику сравнения символов.
Если символы равны, то продолжаем сравнивать символы из строки с искомой строкой до тех пор пока не найдем несовпадающие символы, как только такие находятся выходим из вложенного цикла и повторяем сравнения повторно.
Вторая проверка срабатывает в случае, если мы дошли до конца, и все значения совпали, то мы возвращаем индекс первого символа искомого слова в строке. В противном случае возвращаем -1, что означает что строка не найдена.

Плюсы использования:

• Простота реализации и понимания;

• Работает для любых типов данных, включая текстовые, числовые и т.д.

Минусы использования:

• Низкая производительность, особенно на больших строках и при поиске длинных подстрок;

• Использование большого количества времени и памяти.

“Алгоритм Робина - Карпа”

Алгоритм Робина - Карпа является одним из эффективных алгоритмов поиска, он основан на концепции хеширования.

Принцип работы алгоритма заключается в следующем:

• Сначала происходит вычисление хешей для первого окна тестов строки и подстроки;

• Далее происходит последовательное сравнение хешей. Если хеши совпадают, то происходит дополнительное сравнение посимвольно. Если совпадение найдено - алгоритм завершается;

• Если совпадение не найдено- вычисляется хеш-значение следующей подстроки путем сдвига окна на один символ вправо и вычисления хеш-значения для новой подстроки;

const strStr = (haystack, needle) => {
  const haystackLen = haystack.length
  const needleLen = needle.length

  const prime = 101
  const d = 256

  let haystackHash = 0
  let needleHash = 0
  let fastHash = 1

  // Цикл 1
  for (let i = 0; i < needleLen - 1; i++) {
    fastHash = (fastHash * d) % prime
  }

  // Цикл 2
  for (let i = 0; i < needleLen; i++) {
    haystackHash = (d * haystackHash + haystack.charCodeAt(i)) % prime
    needleHash = (d * needleHash + needle.charCodeAt(i)) % prime
  }

  // Цикл 3
  for (let i = 0; i <= haystackLen - needleLen; i++) {
    if (needleHash === haystackHash) {
      let j

      for (j = 0; j < needleLen; j++) {
        if (haystack[i + j] !== needle[j]) {
          break
        }
      }

      if (j === needleLen) {
        return i
      }
    }

    if (i < haystackLen - needleLen) {
      haystackHash = (d * (haystackHash - haystack.charCodeAt(i) * fastHash) + haystack.charCodeAt(i + needleLen)) % prime
  
      if (haystackHash < 0) {
        haystackHash = (haystackHash + prime)
      }
    }
  }

  return -1
}

Теперь подробнее расскажу про функцию поиска.
1-й цикл используется для вычисления значения, которое используется для ускорения вычисления хешей, она работает по алгоритму fastHash = d^(needleLen-1) % prime.
2-й цикл просто вычисляет хеш для строки и подстроки.
Ну а в 3-м цикле происходят поиск совпадений. Если значения хешей совпадают то, проверяем их по отдельности, если встречается не совпадение, то выходим из цикла и повторяем поиск совпадений, если же все символы совпали, то просто вернем индекс первого элемента.
Если значения хешей не совпадают, то вычисляем значения хеша нового окна для следующего сравнения и повторяем поиск совпадений.

Плюсы использования:

• Быстрый поиск подстроки в среднем случае, особенно для длинных строк и подстрок;

• Возможность эффективного поиска нескольких подстрок сразу, используя одинаковый хеш-код для всех искомых подстрок;

• Хеширование позволяет пропустить множество неподходящих подстрок, сокращая количество необходимых сравнений;

Минусы использования:

• В некоторых случаях, например, при использовании простых хеш-функций, возможны ложные совпадения, которые необходимо дополнительно проверять посимвольно;

• Необходимость выбора эффективной хеш-функции, которая не только быстро вычисляет хеш-значения, но и максимально равномерно распределяет их по всем возможным значениям;

• Если встречаются слишком маленькие или слишком большие хеш-значения, то может возникнуть проблема переполнения, которую необходимо обрабатывать;

Подробнее можно почитать тут

“Алгоритм Кнута - Морриса - Пратта (КМП)”

На данный момент этот алгоритм считается самы быстрым, так как он выполняется за линейное время. Он полезен, когда необходимо провести поиск в большом кол. данных. Также узнал, что данный алгоритм используют не только в поиске подстроки:

• Поиск вхождений гена в последовательности ДНК;

• Автодополнение в поисковых движках;

• Распознавание сигналов в цифровой обработке сигналов;

Ну а теперь перейдем к самому алгоритму. Алгоритм KMP строит таблицу префиксов (это основная часть алгоритма) для подстроки и использует ее для определения наилучшей позиции для продолжения поиска, когда происходит несовпадение символов.
Таблица префиксов - содержит информацию о наибольшем префиксе, который одновременно является суффиксом (т.е. подстрокой, которая начинается с начала строки) этого элемента.

Вот пример реализации префикс функции:

const prefix = (str) => {
  const n = str.length
  const p = Array(n).fill(0)

  let i = 1, j = 0

  while (i < str.length) {
    if (str[i] === str[j]) {
      p[i] = j + 1
      i ++
      j ++
    } else {
      if (j === 0) {
        p[i] = 0
        i ++
      } else {
        j = p[j - 1]
      }
    }
  }

  return p
}

Пример: для строки "abcabcd" префикс функция будет выглядеть следующим образом:
[0, 0, 0, 1, 2, 3, 0], где первые три элемента равны 0, потому что ни один префикс не является суффиксом первых трех символов;
1, 2 и 3, потому что "a", "ab" и "abc" являются префиксами, которые также являются суффиксами; и наконец, последний элемент равен 0, потому что "abcabc" является префиксом строки "abcabcd", но не является суффиксом последнего элемента "d".

После того, как реализована префикс-функция можно прейти к реализации алгоритма поиска. Суть алгоритма заключается сравнении символов строки и подстроки, в случае если символы не равны- мы берем значение из таблицы префиксов и используем его как индекс для перехода, таким образом, мы можем пропускать некоторое количество символов, что позволяет быстрее найти нужную подстроку.

const findStr = (str, searchString) => {
  const searchStringPrefix = prefix(searchString)
  let i = 0, j = 0

  while (i < str.length) {
    if (str[i] === searchString[j]) {
      j ++
      i ++

      if (j === searchString.length) {
        return i - searchString.length
      }
    } else {
      if (j > 0) {
        j = searchStringPrefix[j - 1]
      } else {
        i ++
      }
    }
  }

  if (i === str.length && j !== searchString.length) {
    return -1
  }
}

Плюсы использования:

• Линейное время выполнения: O(n+m), где n - длина строки, m - длина подстроки;

• Эффективно обрабатывает большие тексты с множеством вхождений;

Минусы использования:

• Требует заранее построенной таблицы префиксов, что может занять O(m) времени и O(m) памяти;

• Может быть сложным для понимания и реализации, особенно для новичков в программировании;

Также хочу отметить, что КМП дает выигрыш только в случае если в таблицы префиксов есть положительные значения. Лишь в этом случае указатель будет сдвигается более чем на единицу. Но даже в случае “всех нулей” в таблице поиск работает достаточно неплохо.

Подробнее про то, как реализована префикс-функция и сам алгоритм можно посмотреть тут

Уже перед публикацией нашел несколько статей про алгоритмы поиска, где автор очень подробно описал, как они работают и привел примеры скорости работы:
Алгоритм Кнута - Морриса - Пратта
Алгоритм Бойера - Мура
Алгоритм Рабина - Карпа

Надеюсь эта статья была для Вас полезна. Спасибо!