我们有两个字符串a和b分别。的长度a大于或等于b。我们必须找出最长的公共子串。如果有多个答案，那么我们必须输出早于b（早于其起始索引在先）的子字符串。
a
b
注意：所述的长度a和b可多达10 6。
我试图找到使用后缀数组的最长公共子字符串（使用quicksort对后缀进行排序）。对于一个以上答案的情况，我尝试将所有公共子字符串推入堆栈中，这些字符串等于最长的公共子字符串的长度。
我想知道是否有更快的方法？
构建一个字符串的后缀树a$b，即，a将某个字符与$两个字符串中都没有出现的字符串联起来，然后与串联b。（压缩的）后缀树可以在O（| a | + | b |）时间和内存中构建，并具有O（| a | + | b |）个节点。
a$b
$
现在，对于每个节点，我们都知道其深度（从根开始并遍历树到该节点所获得的字符串的长度）。我们还可以跟踪两个布尔量：是否在与相对应的构建阶段访问过该节点a，以及是否在与相对应的构建阶段访问了该节点b（例如，我们最好分别构建两个树，然后将它们合并使用预遍历）。现在，任务归结为找到在两个阶段都访问过的最深顶点，这可以通过单个预遍历来完成。多个答案的情况应易于处理。
此Wikipedia页面包含该技术的另一（简要）概述。
