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

我有两个字符串，必须对其进行相似性比较。该算法必须设计为找到最大相似度。在这种情况下，排序很重要，但插入（或缺失）的字符不会。由于各种原因，编辑距离在这种情况下不能使用。在字符串中查找部分子字符串

情况基本如下：

string 1: ABCDEFG 
string 2: AFENBCDGRDLFG

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

我现在有一个递归解决方案，但因为这必须在大量运行的数据，任何改进将不胜感激

你可以发布你当前递归解决方案的描述吗？ – Ani 2010-09-20 03:19:31

你有这种语言吗？ – griegs 2010-09-20 03:21:24

只是我，还是这个NP难？ – 2010-09-20 03:21:35

看看你的唯一例子，它看起来像你想找到最长的共同点子序列。看看LCS

难道只是我，还是这个NP-hard？ - 大卫Titarenco（来自评论）

如果你想LCS的任意数量的字符串它的NP-hard。但是它的输入字符串的数量是不变的（在这种情况下是2），这可以在多项式时间内完成。

2010-09-20 03:19:49 codaddict

+1好回答:) – 2010-09-20 03:44:41

这是不对的。根据OP的示例输入，它会返回'ABCDFG' – aaronasterling 2010-09-20 04:04:13

@Aaron：您必须稍微修改一下算法以找到有助于答案的实际子字符串。但基本的想法仍然非常相似。 – codaddict 2010-09-20 05:23:38

回答