Какой самый быстрый способ найти все вхождения подстроки?

Question

Это чисто из любопытства. Я просматривал статью, сравнивающую различные алгоритмы поиска строк, и заметил, что все они предназначены для поиска первой подходящей подстроки. Это заставило меня задуматься ... Что если я захочу найти все вхождения подстроки?

Я уверен, что мог бы создать цикл, который использовал бы вариант KMP или BM и помещал каждое найденное вхождение в массив, но вряд ли это было бы самым быстрым.

Не лучше ли алгоритм «разделяй и властвуй»?

Например, допустим, вы ищете последовательность «abc» в строке «abbcacabbcabcacbccbabc».

1. На первом проходе найдите все вхождения первого персонажа и сохраните их позиции.
2. На каждом дополнительном проходе используйте позиции из предыдущего прохода, чтобы найти все вхождения следующего символа, уменьшая число кандидатов на следующий проход с каждой итерацией.

Учитывая легкость, с которой я пришел к этой идее, я предполагаю, что кто-то уже придумал и улучшил ее 30 лет назад.

Answer 1

См. Массив суффиксов

Приложения

Массив суффиксов строки может быть используется в качестве индекса для быстрого поиска каждое вхождение подстроки в строка. Нахождение каждого вхождения подстроки эквивалентно найти каждый суффикс, который начинается с подстрока. Благодаря лексикографическое упорядочение, эти суффиксы будут сгруппированы в массив суффиксов, и может быть найден эффективно с бинарным поиском. Если реализовано прямо, это бинарный поиск занимает O (mlogn) время, где m - длина подстрока. Чтобы избежать повторения сравнения, дополнительные структуры данных давая информацию о самом длинном общие префиксы (LCP) суффиксов построено, давая O (m + logn) поиск время.

Answer 2

Если вы обрабатываете данную строку только один раз, массив суффиксов является избыточным. Создание занимает O (n log n) времени, поэтому алгоритм в стиле KMP превзойдет его. Кроме того, если ваша строка огромна, или вы хотите получать результаты в режиме реального времени при получении строки, массив суффиксов не будет работать.

Конечно, можно изменить алгоритм KMP, чтобы он продолжал работать после того, как обнаружит совпадение, не занимая дополнительную память, кроме памяти, используемой для хранения совпадений (что также может быть ненужным, если вы просто распечатываете совпадения) или обрабатывать их по ходу дела). Для начала возьмем реализацию Википедии и изменим оператор return m на «добавить m в список индексов». Но вы еще не закончили. Вы также должны спросить себя, разрешаете ли вы перекрывающиеся события? Например, если ваша подстрока «abab» и вы смотрите в основной строке «abababab», есть два случая или три? В приведенном мною примере («как начало») вы можете либо сбросить i на 0, чтобы дать ответ «два», либо перейти к случаю «иначе» после «add m», чтобы дать «три» "ответ.

Answer 3

Не существует единого «самого быстрого пути» это зависит от

A) Из чего строится строка (длина, распределение символов, ...)

B) На каком оборудовании это работает

C) Если вы хотите, чтобы все результаты были параллельными или последовательными

D) Другие параметры (например, могут ли найденные элементы перекрываться, ищите ли вы один или несколько раз)

E) Если вы видите эту реализацию специфической или просто академической. В реализации есть много дополнительных способов оптимизации вещей. Например. временное хранение (как в вашем предложении) часто очень дорого.

Идея, которая у вас есть, например. будет полностью уничтожить любой кэш процессора для длинных строк. Так что в таких случаях это будет ОЧЕНЬ медленно.

Answer 4

И KMP, и BM легко можно использовать для поиска нескольких совпадений. Я также рекомендовал бы использовать Рабина-Карпа , что, IMHO, легче понять, но не так быстро для нескольких совпадений (O (n + k * m), я думаю, где n - длина текста m - длина шаблона, а k - количество вхождений). Но это легко изменить как для перекрывающихся, так и для непересекающихся совпадений.

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