如何從同一位置找到所有可能的最長公共子序列

Question

我想從多個固定長度字符串的相同位置找到所有可能的最長公共子序列（總共有700個字符串，每個字符串有25個字母） 。最長的公共子序列必須包含至少3個字母，並且至少包含3個字符串。所以，如果我有：

String test1 = "abcdeug"; 
String test2 = "abxdopq"; 
String test3 = "abydnpq"; 
String test4 = "hzsdwpq"; 

我需要的答案是：

String[] Answer = ["abd", "dpq"]; 

我的一個問題是，這必須儘可能快。我試圖用後綴樹來查找答案，但後綴樹方法的解決方案是["ab","pq"].Suffix樹只能從多個字符串中找到連續的子串。常用的最長的公共子序列算法不能解決這個問題。 有沒有人有任何想法如何以低時間成本解決這個問題？ 謝謝

Answer 1

我建議你在嘗試使用任何聽起來像它可能會做你想要的算法之前將此投射到一個衆所周知的計算問題。

這是我的建議：將其轉換爲圖形問題。對於字符串中的每個位置，創建一組節點（對於集合中所有字符串中該位置的每個唯一字母都有一個節點...如果所有700個字符串在相同位置不同，則爲700個節點）。一旦爲字符串中的每個位置創建了所有節點，就會檢查一組字符串，查看兩個位置共享多於3個相等連接的頻率。在你的例子中，我們先看看位置1和2，看到三個字符串在位置1包含「a」，在位置2包含「b」，因此我們在第一組節點中的節點「a」之間添加有向邊在第二組節點中「b」（繼續對所有位置對和這兩個位置中的所有字母組合進行此操作）。您可以爲每個職位組合執行此操作，直到您添加了所有必要的鏈接。

一旦你有你的最終圖，你必須尋找最長的路徑;我建議您在這裏查看維基百科文章：Longest Path。在我們的例子中，我們將有一個有向無環圖，你可以在線性時間內解決它！預處理應該是字符串位置數量的二次方，因爲我想你的字母大小是固定的。

P.S：您向我發送了一封關於我正在處理的雙聚算法的電子郵件;它尚未公佈，但將於今年某個時候發佈（，指頭交叉）。感謝您的興趣:)

Answer 2

您可以嘗試使用哈希。
每個字符串最多有25個字符。這意味着它有2^25個子序列。你拿每個字符串，計算所有2^25哈希值。然後你加入所有字符串的所有散列並計算它們中至少包含3次。 爲了獲得這些子序列的長度，您不僅需要存儲散列，還需要存儲對<hash, subsequence_pointer>，其中subsequence_pointer確定該散列的子序列（最簡單的方法是枚舉所有字符串的所有散列並存儲散列號）。
根據算法，最壞情況下的程序（700個字符串，每個25個字符）將運行幾分鐘。