在N個字符串中查找公共子字符串的算法

我熟悉2個字符串的LCS算法。尋找有關在2..N個字符串中查找常見子字符串的建議。每對中可能有多個常見的子串。在字符串的子集中可以有不同的常用子字符串。在N個字符串中查找公共子字符串的算法

字符串：(ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

常見字符串：

1/2 (DEF) 
1/3 (ABCDEF) 
1/4 (IJKL) 
1/5 (FGH) 
2/3 (DEF)

最長的公共字符串：

1/3 (ABCDEF)

最常見的字符串：

1/2/3 (DEF)

來源

2010-03-10 Dwight Kelly

這是一個需要具有一定性能的算法的ACM競賽問題嗎？ – Roman 2010-03-10 16:23:52

子字符串'F'是不是最常見的，因爲它出現在四個字符串中？ – interjay 2010-03-10 16:24:17

這是一個好主意，告訴我們爲什麼你需要這個，所以我們可以瞭解我們可以妥協的地方，哪裏不能。 – 2010-03-10 16:27:05

這SOR在DNA序列分析中一直都是做事情的東西。你可以找到它的各種算法。列出了一個合理的收集品here。

還有一個蠻力的方法，每子字符串（如果你只對短的感興趣）製作的表格：形成一個N元樹（N = 26代表字母，256代表ASCII）級別，並存儲每個節點的計數直方圖。如果刪除少量使用的節點（爲了保持內存需求合理），您最終將得到一個算法，該算法可以找到所有長度爲M的子序列，例如輸入長度爲N * M^2 * log（M）的時間N.如果你把它分成K個單獨的字符串，你可以建立樹結構，並通過樹中的一次讀取答案（s）。

來源

2010-03-10 17:15:35

幾乎都這麼說，這一直被用於計算生物學。然而，「substring/subsequence」的定義往往是模棱兩可的（對於非算法專家而言並非如此），我認爲在這種情況下，他的問題要求它們是連續的。 – Larry 2010-03-10 18:25:33

後綴樹是答案，除非你有真正的大字符串，內存成爲一個問題。預期字符串中每個字符的內存使用量爲10〜30個字節，以實現良好的實現。還有一些開源實現，這可以讓你的工作更輕鬆。

還有其他一些更具吸引力的算法，但它們很難實現（查找「壓縮後綴樹」）。

來源

2010-03-10 17:31:48 luispedro

在N個字符串中查找公共子字符串的算法

回答

相關問題