Нахождение частичных подстрок в строке

Question

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

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

string 1: ABCDEFG
string 2: AFENBCDGRDLFG

результирующий алгоритм найдет подстроки A, BCD, FG

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

Answer 1

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

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

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