получение строки из списка подстрок

Question

Я попросил решить следующую задачу в конкурсе по программированию (набор в Facebook)

Ввод: список подстрок:

{"bar","foo","hi"} //from 1 to 100 sub-strings 

и предложение:

"hellothisisfoobarhi" //from 1 to 1000000 character

Вывод: 12 // индекс первого совпадения в предложении (foo)

другой пример:

подстроки: {"hi", "hi"}

предложение: "hiJonIamSayinghihiforYou"

output: 15 // индекс hi, второй 'hi', потому что первый 'hi' - это просто трюк, подстатья 'hi 'hi "

еще один пример:

подстроки: {" hi "," foo "}

предложение:" sayfoohi "

output: 6 // порядок не имеет значения, они просто должны быть рядом друг с другом

Кто знает хороший алгоритм для этой проблемы?

Answer 1

Построить дерево суффиксов большой строки - конструкция дерева имеет вид O (n), где n - длина большой строки.

Теперь вы можете найти расположение любой из подстрокза время O (m) (где m - длина подстроки), просто следуя подстроке вниз по дереву - узлу или листу, где заканчивается подстрока, будет удерживаться ключ, соответствующий индексу, в большую строку.

Просмотрите набор подстрок, находя их расположение в большой строке, отслеживая минимальный индекс.

Answer 2

Другой способ - сосредоточиться на подстроках, а не на основной строке - будет http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm