首先要想办法能快速判断两个字符串在最小表示法下的字典序大小，主要利用两点： 相同字符在最小表示法下的大小关系也是相同的； 对字典序大小关系”起决定性因素的“是第一个不同的字符  于是考虑把每个字符单独拆开看，先预处理出每个后缀 S[i:]S[i:]S[i:] 从位置 iii 开始往后第一个出现、第二个出现的字符是什么。比较两个后缀 S[i:]S[i:]S[i:] 和 S[j:]S[j:]S[j:] 的字典序时，从小到大枚举第 kkk 大(也就是第 kkk 个出现的字符)，想办法匹配出第一个 ”不同构“(见下面图解) 的位置；最终所有 26 个字符第一个 ”不同构“ 的位置取最小值，就是两个...

后缀数组做法  后缀数组的做法一般都包括三个数组：sasasa：所有后缀中字典序第 iii 大的是从位置 sa[i]sa[i]sa[i] 开始的后缀； rankrankrank：位置 iii 开始的后缀在所有后缀中字典序排第 rank[i]rank[i]rank[i]； lcplcplcp：高度数组，字典序第 iii 大得缀与字典序第 i+1i+1i+1 大的后缀的最长公共前缀(longest common prefix)。另外通过建立 lcplcplcp 上的 st表，可以求得任意两个后缀 xxx 和 yyy 的最长公共前缀： query_min(rank[x],rank[y]−1),这里假...