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

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

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

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

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

const findStr = (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 findStr = (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) памяти;

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

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

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

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

Алгоритм Кнута — Морриса — Пратта
Алгоритм Бойера — Мура
Алгоритм Рабина — Карпа

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