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 在我看來，它是二次的。

只有加速似乎是一個字典，以獲得使用給定字符的所有索引。這將時間減少了一個因素，即使用不同字符的數量。