Найти любой из набора подстрок в строке эффективно

Question

Предположим, у нас есть 3 строки: "ab", "cd" and "ef".
Предположим, что подстрока, которую мы хотим найти, является перестановкой вышеупомянутых строк, то есть any of {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf"}
Теперь предположим, что у нас есть длинная строка, и мы хотим найти в ней любую из подстрок из указанного выше набора (немного упростить случай и предположить, что в основной строке есть только одно вхождение только одной из этих подстрок). ).
например.

Main string: abcdghefcdabgh
Substring:         efcdab

Каким будет самый эффективный способ поиска в этом случае? Выполнение грубой силы и поиск каждой возможной подстроки крайне неэффективны.
Рабин-Карп для поиска по нескольким шаблонам - один из методов, который мне приходит в голову. Однако я не уверен, какой будет очень эффективная хеш-функция в этом случае.

Answer 1

ищите любой «ab», найдите «cd» или «ef» в +1 или -1, продолжайте, пока не будет найдена вся перестановка.

пример:

с использованием "ab", "cd", "ef"
в "asjkdnjdnaboidnabefcdasdnmk"

первый экземпляр "ab" находится в 9, таким образом:

lowerFound = 9
upperfound = 11 \\ found index + length of found string

оттуда вы знаете, что любое другое совпадение в перестановке должнолибо перед lowerfound, либо над upperfound, поэтому посмотрите на обе стороны, например:
dn ab oi не содержит совпадений, поэтому отбросьте и найдите следующий "ab" в 15

lowerFound = 15
upperfound = 17
search for "cd" or "ef" at 15-length or 17
found "ab"+"ef"

lowerFound = 15
upperfound = 19
search for "cd" at 15-length or 19
found "abef"+"cd"

return

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

Answer 2

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

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

Другим более быстрым методом, который потребует некоторого дополнительного пространства, будет создание дерева суффиксов в тексте.А затем сопоставьте каждый из шаблонов.Создание дерева - это O (n), где n - размер текста.Соответствие каждому шаблону - O (p), где p - длина каждого шаблона.

Общее время = O (p1 + p2 + p3 ... + n)