python - python的difflib.find_longest_match是怎么实现的？

Question

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

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

尝试使用 python 的 difflib.find_longest_match，速度更快(但仍然不如 id 那样快)。

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

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

谢谢。

Answer 1

这是代码:http://svn.python.org/view/python/tags/r271/Lib/difflib.py?view=markup在我看来，它是二次方的。

Only speedup 似乎是一个字典，用于获取使用给定字符的所有索引。这将时间减少了一个因素，即使用的不同字符的数量。