SA (Suffix Array) -- 后缀数组
简介
这里明白两个定义：
\(SA_i\) : 按字典序排列后大小为 \(i\) 的后缀的后缀头的下标。
\(Rank_i\) : 后缀头的下标为 \(i\) 按字典序排列后的排名。
一个显而易见却很重要的结论:
\[SA[Rank[i]] = Rank[SA[i]] = i \]如何进行后缀排序？
暂且挂 oi-wiki , 有时间再写...乐
\(height\) 数组
你会后缀排序却不会 \(height\) 数组就像你会求 \(Next\) 数组却不会 \(KMP\) 匹配一样。 —— Wang54321
定义一个东西： \(height_i\) 表示 \(Rank\) 为 \(i\) 的和 \(Rank\) 为 \(i - 1\) 的的 \(LCP\)
即 \(LCP(i , i - 1)\)
求的方法：
略。先不写了。乐。
后缀数组的用途
其实主要是 \(height\) 数组哈。
挂俩题，并题解：
AHOI差异(vjudge) —— 题解(在字符串里找一下)
Yet Another LCP Problem(题解和题意)
标签：--,Rank,height,后缀,数组,SA From： https://www.cnblogs.com/hangry/p/18126385