最初想要一个算法来找到两个 python 字符串之间的最长子字符串。最佳运行时的一般答案是“构建后缀树”，基于线性运行时的在线共识。然而，网上关于这方面的例子为零，这并不奇怪，因为后缀树被认为是非常复杂和不直观的构造。

我实现了一个 DP 解决方案（它仍然是二次的）并且对于我正在尝试做的事情来说太慢了。

尝试使用 python 的 difflib.find_longest_match，它更快（但它仍然不如 id 那样快）。

所以如果有人知道， find_longest_match() 方法使用什么算法？

另外，如果 find_longest_match() 的算法不是最优的，有谁知道哪里可以找到线性最大子串算法是如何实现的。这是一个有点著名的问题，奇怪的是在线上的最优解决方案如此之少甚至没有。或者我可能只是被误导了，下限是二次的，甚至是 nlogn。

谢谢。

这是@cgrand对“Clojure Performance For Expensive Algorithms”问题的回答的后续。我一直在研究它，并尝试将他的一些技术应用到我自己的实验性 Clojure 性能调优中。

我想知道的一件事是“丑陋的”“数组交换技巧”

与原始方法相比，这如何以及为什么会提高性能？我怀疑 Clojure 数组有时不是真正的 Java 原始数组？如有必要，请在您的回答中引用 Clojure 核心源。

我有这个程序，它应该找到多个字符串的最长公共子字符串。它确实如此，但如果字符串很长（即> 8000 个字符长），它的工作速度很慢（1.5 秒）。有什么办法可以优化吗？

程序是这样的：

注意：我没有编写可以用后缀树解决这个问题的代码是有原因的（它们很大）。

I was wondering if anyone knows how to simplify, or generalize this code. It gives the correct answer, however it is only applicable to the current situation. My code is as follows:

My question is, in the second if statement, I have it set to a set amount of that pattern being repeated (applicable for the string we were given). However, is there a way to keep doing a while loop to search through the \2 (pattern repeat)? What I mean is can this: if ($someSequence =~ m/(([A][T])\2\2\2\2\2)/g) be simplified and generalized with a while loop

我已经实现了最长公共子序列算法并获得了最长的正确答案，但无法弄清楚如何打印出构成最长公共子序列的内容。

也就是说，我成功获得了最长公共子序列数组的长度，但我想打印出最长的子序列。

这段代码的操场在这里

http://play.golang.org/p/0sKb_OARnf

当我尝试在选项卡更新时打印出子序列时，结果是重复的。我想为 str1 和 str2 打印出类似“GTABTABTABTAB”的内容

提前致谢。

我的代码适用于计算 LCS 的长度，但我在以下链接上应用相同的代码来读取 LCS，

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

但缺少一些字符串。你能告诉我我错过了什么吗？

谷歌游乐场链接： http ://play.golang.org/p/qnIWQqzAf5

提前致谢。

我需要从 C++ 中的一组文件名中计算最长的公共子字符串。

准确地说，我有一个 std::list 的 std::strings （或 QT 等价物，也可以）

我需要计算所有字符串的 n 个不同的最长公共子字符串，在这种情况下，例如对于 n=2

如果我能计算出最长的公共子序列，我可以把它剪掉并再次运行算法以获得第二长的，所以基本上这归结为：

是否有（参考？）实现来计算 std::strings 的 std::list 的 LCS？

这不是一个好的答案，而是我拥有的一个肮脏的解决方案 - 对 QUrls 的 QList 进行暴力破解，其中仅获取最后一个“/”之后的部分。我很想用“正确的”代码替换它。

（我发现了http://www.icir.org/christian/libstree/ - 这会很有帮助，但我无法在我的机器上编译它。也许有人用过这个？）

我有一对字符串，例如：abcabcabcandabcxxxabc和一个公共子串对列表 (LCSP)，在这种情况下 LCSP 是 6 对，因为abc第一个字符串中的三个映射到abc第二个字符串中的两个。现在我需要找到最长的有效（递增）对序列，在这种情况下，有三个同样长的解决方案：（ 0:0,3:6; 0:0,6:6; 3:0,6:6这些数字是原始字符串中每对的起始位置，子字符串的长度为 3 作为 "abc ”）。我将其称为最长子串对序列或 LSPQ。（Q是不要混淆String和Sequence）

这是此示例的 LCSP：

现在我发现它用蛮力递归地尝试所有组合。所以我限制在25对左右，否则不实用。Size=[10,15,20,25,26,30], Time ms = [0,15,300,1000,2000,19000]

有没有办法在线性时间或至少不是二次复杂度内做到这一点，以便可以使用更长的输入 LCSP（公共子串对列表）。

这个问题类似于“最长公共子序列”，但不完全是，因为输入不是两个字符串，而是一个按长度排序的公共子字符串列表。所以我不知道在哪里寻找现有的解决方案，或者即使它们存在。

这是我的特定代码（JavaScript）：

在Common Child的编程挑战中，我采用了与一般最长公共子串问题不同的方法。该代码是

采用较小的测试用例我能够获得解决方案，但我无法获得更长的解决方案。

我所做的是

输入：ABCDEF - 设为 FBDAMN - 设为 b，因为它已插入代码中。输出：2。即。因为 BD 是子字符串。

所以我在这里做的是检查a的每个子字符串的可匹配子字符串，并打印最大的。IE。ABCDEF, BCDEF,CDEF,DEF,EF,F 的子字符串，表示此处的最外层循环。（循环 i）

现在第二个循环匹配字符串中的每个字母，即。它迭代 (1...n),(2...n),(3...n),...,(n)，这意味着它从 i 指定的字母开始。

现在第三个循环遍历整个字符串 B 以查看 a[j] 是否与 B 中的任何字母匹配，如果是，则 count 递增。

由于我们只能从子字符串中删除字母而不是弄乱它，即每个字母在两个字符串中应该具有相同的相对顺序，因此我在找到前一个字母后使用 x 搜索 B。

试运行就像示例（从 0 到 n-1 的数组）

a= abcdef b= fbdamn

当 i=0 - 整个字符串匹配 abcdef

x=-1 所以 k 从 0 迭代到 n-1 所以，a=f？a=b？a=d? 一个=一个？计数=计数+1；所以x设置为3（a的位置）。A 中的 a 之后的元素只能出现在 B 中的 a 之后，因此 x=3。因此 k 从 4 迭代到 5 b=m？b=n? c=m?c=n? ………………

现在我们保存先前计数的值，如果它大于之前的计数。所以 maxcount=count 然后将 count 重置为 0，并重置位置 x=-1。

i=1 即字符串 = BCDEF k 从 0 到 n 所以，B=F？b=b？count=count+1 // 变为 1 x 设置为 1(B 的位置) k 从 2 到 nc=d? c=a?c=m?c=n? k 从 2 到 nd=d？count = count+1 // 变为 2 x 设置为 2 k 从 3 到 ne=a?e=m?e=n? k 从 3 到 nf=a?f=m?f=n? 然后如果最大计数（代码中的prev）大于当前计数，则maxcount = count，重置count = 0，x = -1；然后对于 CDEF,DEF,EF,F 就这样了，这里的最大子字符串变成了 2

适用于较短的测试用例，但不适用于较长的测试用例。

它适用的测试用例是：

OUDFRMYMAW AWHYFCCMQX

带输出 2

不适合

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正确的输出是15，我的输出是10。任何人都可以向我解释我在哪里犯了错误

高水平

我正在尝试折叠句子列表中的常见子字符串，并仅显示它们不同的区域。所以采取这个：

并返回：

更多细节

• 我一直在研究最长的公共子串算法，但这似乎只比较两个字符串。
• 我只对比较字符串中的整个单词感兴趣。
• 只想从左到右评估字符串。
• 不常见子串的长度不会是相同的词数（“猫”与“花园蛇”）

我正在寻求有关算法的帮助。我相信这是 LCS 问题的变体，我认为是对后缀树的某种处理。可以解释和实现的伪代码将是理想的。

另一个例子

变成：

也许这种方法

这种方法怎么样...