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

假设我想查找最长的子序列，使得子序列的前半部分与后半部分相同。查找字符串中最长的相似子序列

例如：在字符串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

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

回答

相关问题