Алгоритм для сопоставления последовательного подмножества из списка

Question

Я пытаюсь запомнить правильный алгоритм для поиска подмножества в наборе, который соответствует элементу списка возможных подмножеств. Например, если входной сигнал:

aehfaqptpzzy 

и список подмножество:

{ happy, sad, indifferent } 

мы можем видеть, что слово «счастливый» является матч, потому что он находится внутри ввода:

a e h f a q p t p z z y

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

UPDATE

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

вход: acegimnrqvy

словарь: {НКЗ, DFR, LMR, mnqv, например}

Таким образом, в этом примере алгоритм будет возвращать CGN, mnqv и, например, как Матчи. Кроме того, я хотел бы найти лучший набор дополнительных матчей, где «лучший» означает самый длинный. Таким образом, в приведенном выше примере «лучшим» ответом будет «cgn mnqv», например, не будет соответствовать, потому что он конфликтует с cgn, который является более длинным.

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

Answer 1

Вы можете использовать алгоритм Aho - Corrasick с более чем одним текущим состоянием. Для каждой из входных букв вы либо остаетесь (пропустите букву), либо двигайтесь с использованием соответствующего края. Если два или более «актера» встречаются в одном и том же месте, просто объедините их с одним (если вас интересует только присутствие и не считается).

О сложности - это может быть так же медленно, как наивный подход O(MN), потому что может быть до size of dictionary актеров. Однако на практике мы можем хорошо использовать тот факт, что многие слова являются подстроками других, потому что никогда не будет больше, чем size of the trie актеров, которые - по сравнению с размером словаря - имеют тенденцию быть намного меньше.