Поиск частичных подстрок внутри строки

Question

У меня есть две строки, которые нужно сравнить для подобия. Алгоритм должен быть разработан, чтобы найти максимальное сходство. В этом случае порядок имеет значение, но промежуточные (или отсутствующие) символы этого не делают. Расстояние редактирования не может использоваться в этом случае по разным причинам.

Ситуация в основном следующим образом:

string 1: ABCDEFG 
string 2: AFENBCDGRDLFG 

полученный алгоритм найдет подстроку A, BCD, FG

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

Answer 1

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

Это только меня, или это NP-трудной? - Дэвид Титаренко (от комментариев)

Если вы хотите, чтобы LCS произвольного количества строк было NP-жестким. Но это число входных строк является постоянным (как в этом случае 2) это можно сделать в полиномиальное время.