后缀数组 SA

一句话理解

后缀数组把所有后缀排序。

为什么要学

sa[i] 第 i 小后缀起点。

讲解

倍增或 SA-IS。配合 height。

例子

字符串的所有尾巴排序。

常见错误

• n=1e6 还 n² 排序后缀。
• 和后缀自动机混淆。