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

我有兩個字符串，必須對其進行相似性比較。該算法必須設計爲找到最大相似度。在這種情況下，排序很重要，但插入（或缺失）的字符不會。由於各種原因，編輯距離在這種情況下不能使用。在字符串中查找部分子字符串

情況基本如下：

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

回答