Алгоритмы поиска подстроки на JavaScript
Недавно я столкнулся с одной не очень сложной задачей на leetcode. В рамках задачи нужно было реализовать алгоритм поиска подстроки в строке. Пока я пытался сделать задачу, я понял, что я очень мало знаю про то как можно искать подстроку и решил изучить эту тему подробнее, и рассказать результат вам.
Как говорит Википедия “Поиск подстроки в строке — одна из простейших задач поиска информации”, но это не совсем так, ниже я расскажу про разные алгоритмы решения и покажу примеры их реализации. Начнем!
“Алгоритм грубой силы” или “Алгоритм простого поиска”
Алгоритм грубой силы — это простой алгоритм поиска подстроки, он заключается в последовательном переборе всех символов строки и проверки совпадения с искомой подстрокой. Если совпадение не найдено, то алгоритм сдвигает искомую подстроку на один символ вправо и начинает поиск снова.
const findStr = (haystack, needle) => < const m = needle.length const n = haystack.length for (let windowStart = 0; windowStart 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 > 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) памяти;
- Может быть сложным для понимания и реализации, особенно для новичков в программировании;
Также хочу отметить, что КМП дает выигрыш только в случае если в таблицы префиксов есть положительные значения. Лишь в этом случае указатель будет сдвигается более чем на единицу. Но даже в случае “всех нулей” в таблице поиск работает достаточно неплохо.
Подробнее про то, как реализована префикс-функция и сам алгоритм можно посмотреть тут
Уже перед публикацией нашел несколько статей про алгоритмы поиска, где автор очень подробно описал, как они работают и привел примеры скорости работы:
Надеюсь, эта статья была для Вас полезна. Спасибо!