Что самый быстрый путь состоит в том, чтобы найти всеми случаями подстроки?

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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