这是本文档旧的修订版!
按照题目给定的最小表示法对字符串进行后缀排序。 考虑在较短时间内对后缀 $S[i:]$ 和 $S[j:]$ 排序,要求在短时间内能求出两后缀的 $Lcp$ 即可。先预处理出每个后缀对应的字符大小关系,并求出每个字符出现位置的差分数组,并建立后缀自动机,在求 $Lcp$ 时需要按相对大小枚举每个字符,求出最早的失配位置,再取最小值就能得到 $Lcp$,注意特判第一个字符。 单次判断复杂度 $O(26)$,排序总复杂度 $O(26\times n\log n$)