查找字符串中的部分子字符串

Question

我有两个字符串,必须比较相似性.必须设计算法以找到最大相似性.在这种情况下,排序很重要,但是干预(或缺失)字符则不然.由于各种原因,在这种情况下不能使用编辑距离.

情况基本如下:

string 1: ABCDEFG
string 2: AFENBCDGRDLFG

所产生的算法将找到的子串A,BCD,FG

我目前有一个递归解决方案,但因为这必须在大量数据上运行,所以任何改进都将非常受欢迎

Answer 1

看看你唯一的例子,看起来你想要找到最长的共同子序列.看看LCS

它只是我,还是这个NP难？ - David Titarenco(来自评论)

如果你想要任意数量的字符串的LCS其NP难.但它输入字符串的数量是恒定的(如在这种情况下,2),这可以在多项式时间内完成.