#string #algorithm #substring
#строка #алгоритм #подстрока
Вопрос:
Предположим, у нас есть 3 строки: "ab", "cd" and "ef" .
Предположим, что подстрока, которую мы хотим найти, является перестановкой вышеуказанных строк,
т.Е. any of {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf"}
Теперь предположим, что у нас есть длинная строка, и мы хотим найти в ней любую из подстрок из приведенного выше набора (немного упрощая случай и предполагая, что в основной строке встречается только одно вхождение только одной из этих подстрок).
например.
Main string: abcdghefcdabgh
Substring: efcdab
Какой будет наиболее эффективный способ выполнить поиск в этом случае? Перебор и поиск каждой возможной подстроки крайне неэффективны.
Рабин-Карп для поиска по нескольким шаблонам — один из методов, который приходит мне на ум. Однако я не уверен, какой будет очень эффективная хэш-функция в этом случае.
Комментарии:
1. Что не так с скользящим хэшем Рабина-Карпа, описанным в Википедии ?
2. Для конкретного случая, который вы описываете, не кажется таким уж неэффективным проверять каждую подстроку строки поиска нужной длины (их O (n) для длины строки поиска n) и посмотреть, является ли это целевой строкой. Если набор целевых строк невелик, вы можете построить хэш-таблицу в O (m) (где m — количество целевых строк)… В противном случае вы могли бы построить какое-то дерево поиска или что-то в этом роде. Я не знаю, как вы думаете, вы можете сделать это лучше, чем O (n m) … извините за плотность, если это упускает что-то очевидное.
3. @robmayoff ну, в этом нет ничего плохого. Я просто хочу знать, есть ли лучший метод, который мне не хватает 🙂
4. @Patrick87 ну, это был вопрос на interviewstreet’s facebook challenge. Случай, который я описал, очень маленький. В вопросе говорилось, что строка для поиска может иметь длину в миллион символов, а количество подстрок, из которых можно выбрать, равно 100! (здесь это 3!)
Ответ №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" , вы можете сохранить уже найденный индекс в памяти.
Ответ №2:
Я не уверен, что возможно найти все перестановки строк шаблонов, но если эти перестановки можно найти за разумное время, то вы можете использовать этот алгоритм для одновременной проверки всех шаблонов.
http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm
Другим более быстрым методом, который потребует некоторого дополнительного пространства, было бы построение дерева суффиксов в тексте. А затем сопоставлять каждый из шаблонов. Создание дерева — это O (n), где n — размер текста. Соответствие каждому шаблону равно O (p), где p — длина каждого шаблона.
Общее время = O(p1 p2 p3… n )