algorithm - 在字符串中查找部分子字符串

Question

我有两个字符串，必须比较它们的相似性。必须设计算法以找到最大的相似性。在这种情况下，顺序很重要，但中间(或缺失)的字符无关紧要。由于各种原因，在这种情况下不能使用编辑距离。

情况基本如下:

string 1: ABCDEFG
string 2: AFENBCDGRDLFG

生成的算法将找到子字符串 A、BCD、FG

我目前有一个递归解决方案，但是因为这必须在大量数据上运行，所以任何改进都将不胜感激

Answer 1

从您的唯一示例来看，您似乎想要找到最长的公共(public)子序列。看看LCS

Is it just me, or is this NP-hard? – David Titarenco (from comment)

如果你想要任意数量字符串的 LCS，它是 NP-hard。但如果输入字符串的数量是常数(在本例中为 2)，这可以在多项式时间内完成。