Недавно я столкнулся с одной не очень сложной задачей на 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) памяти;
Может быть сложным для понимания и реализации, особенно для новичков в программировании;
Также хочу отметить, что КМП дает выигрыш только в случае если в таблицы префиксов есть положительные значения. Лишь в этом случае указатель будет сдвигается более чем на единицу. Но даже в случае “всех нулей” в таблице поиск работает достаточно неплохо.
Подробнее про то, как реализована префикс-функция и сам алгоритм можно посмотреть тут
Уже перед публикацией нашел несколько статей про алгоритмы поиска, где автор очень подробно описал, как они работают и привел примеры скорости работы:
Алгоритм Кнута - Морриса - Пратта
Алгоритм Бойера - Мура
Алгоритм Рабина - Карпа
Надеюсь, эта статья была для Вас полезна. Спасибо!
