老忘后缀数组咋写，写个东西记录下。
算法核心：因为后缀是在同一个串内的，要充分利用其它信息。
考虑倍增，即从小到大按照长度为 \(2^k\) 的串进行排序。
先按照长度为 \(1\) 的串排序，每个点有一个排名。
然后扩展到长度为 \(2\)，现在可以知道每个长度为 \(2\) 的串前一半相对的排名和后一半相对的排名，那么显然是要先按前一半的排，如果相等再按后一半的排，用 pair 加快排可以做到 \(n\log n\)，但是不够。考虑使用基数排序，就可以做到 \(n\) 。
再扩展到长度为 \(4\) …… 总时间复杂度 \(n\log n\)。
光求这个没啥用，考虑求一个 height，表示排名为 i 的后缀和排名为 i-1 的最长公共前缀有多长。那么任意两个后缀的 LCP 就可以直接通过 RMQ 求。
考虑怎么求 height，设 h 表示第 i 串和排名恰好小于它 1 的串的最长公共前缀。那么有 \(h[i]\ge h[i-1]+1\)。如果 \(h[i-1]\leq 1\)，那么显然成立，否则 \(h[i-1]\geq 2\)，假设排名恰好小于第 i-1 串 1 的串是第 k 串，那么就有 \(s[i-1,i-1+h[i-1])=s[k,k+h[i-1])\) 且 \(s[i-1+h[i-1]]>s[k+h[i-1]]\)，那么 \(s[i,i-1+h[i-1])=s[k+1,k+h[i-1])\)，因为 \(h[i-1]\geq 2\)，那么这个区间不为空，又因为 \(s[i-1+h[i-1]]>s[k+h[i-1]]\)，那么第 k+1 串的排名肯定是小于第 i 串的，而距离 i 越远 LCP 就越小，那么第 i 串和排名恰好小于它 1 的串的 LCP 至少为 \(h[i-1]-1\) 。所以可以直接从小到大暴力枚举求。