查找字符串中最長的相似子序列

假設我想查找最長的子序列，使得子序列的前半部分與後半部分相同。查找字符串中最長的相似子序列

例如：在字符串abkcjadfbck中，結果爲abcabc，因爲abc在其前半部分和後半部分重複。在aaa中，結果是aa。

來源

2012-04-01 test

我不明白。第一個字符串中的任何地方的'abc'在哪裏？爲什麼第二個字符串的結果不是'aaa'？顯然這更長。 – 2012-04-01 14:36:31

我想子序列並不意味着指數必須是連續的。得到的aa可以是[索引0，索引1]，[索引1，索引2]或[索引0，索引2]。 – DaveFar 2012-04-01 15:32:53

aaa具有「aa」結果，因爲在「aa」上半部分與下半部分相同。 – test 2012-04-01 15:55:59

此任務可能被視爲兩個衆所周知的問題的組合。

如果您事先知道子序列的兩半之間的某個點，您只需要找到兩個字符串的最佳匹配。這是Pairwise alignment的問題。各種動態編程方法在O（N ）時間內解決它。
要找到字符串應該被最佳分割的點，可以使用Golden section search或斐波那契搜索。這些算法具有O（log N）時間複雜度。

來源

2012-04-01 19:43:29

所以，我從你的方法理解是，從i = 1：n，創建兩個字符串，並執行最長的公共子序列。因此，它將是n *（n * n）的次序來找到具有相似一半的最長子序列。但是，我們能不能生成所有這樣的字符串（不只是最長的字符串）？例如，對於aaa，我們將有3個這樣的字符串可能aa，aa，aa。（具有第二個「a」的第一個「a」，具有第三個「a」的第一個「a」，具有第三個「a」的第二個「a」） – test 2012-04-02 08:07:07

用這些算法搜索最長的子序列是O（N^2logN）黃金分割搜索你不需要在每個可能的位置分割字符串。但是這不允許獲得所有子序列。生成所有子序列是完全不同的任務，應該通過其他一些方法來解決。 – 2012-04-02 08:17:52

第一遍通過inputString，我們可以計算每個字符出現的頻率，並刪除出現的那些字符。

input: inputString 
data strucutres: 
Set<Triple<char[], Integer, Integer>> potentialSecondWords; 
Map<Char, List<Integer>> lettersList; 

for the characters c with increasing index h in inputString do 
    if (!lettersList.get(c).isEmpty()) { 
    for ((secondWord, currentIndex, maxIndex) in potentialSecondWords) { 
     if (there exists a j in lettersList.get(c) between currentIndex and maxIndex) { 
     update (secondWord, currentIndex, maxIndex) by adding c to secondWord and replacing currentIndex with j; 
     } 
    } 
    if potentialSecondWords contains a triple whose char[] is equal to c, remove it; 
    put new Triple with value (c,lettersList.get(c).get(0), h-1) into potentialSecondWords; 
    } 
    lettersList.get(c).add(h); 
} 
find the largest secondWord in potentialSecondWords and output secondWord twice;

所以這個算法在陣列上通過一次，創建用於每個索引，它是有意義的，一個三重代表潛在第二字開始當前索引處，並更新所有潛在的第二字。

在合適的列表實現中，n是inputString的大小，該算法具有最壞情況運行時間O（n 2），例如，爲一個^ n。

來源

2012-04-01 15:30:14 DaveFar

你能解釋算法嗎？ – test 2012-04-01 15:56:24

查找字符串中最長的相似子序列

回答

相關問題