后缀数组模版

正文索引 [隐藏]

简介

给定一个 $0-Based$ 字符串 Str,将它的所有后缀进行排序。
数组 $sa[i]$ 中保存排名第 $i$ 的后缀的在字符串的那个位置,数组 $rank[i]$ 表示从位置 i 开始的子串的排名。
数组 $height[i]$ 表示排名第 $i$ 的字符串和排名第 $i+1$ 的字符串的公共前缀长度。

代码