CLICK HERE(LINK)

$\large\text{Outline}$

• 处理本质不同子串，后缀数组是最直接以及性质最强的方式。

$\large\text{Algorithm}$

• 本质不同子串个数，直接考虑后缀数组。
• 若从后方插入一个字符，将影响 $\text{strlen}(S)$ 个后缀，而从前方插入一个字符，只会新增一个后缀。
• 本质不同子串个数与字符串正序或倒序无关，考虑倒置后从前方插入元素。
• 对于两个完全不同的后缀，对答案的贡献为它们的长度之和，如果两串前缀相同，则会算重。因此需要减去它们的 $\text{LCP}$ 长度。
• $\text{LCP}$ 可以通过 $\text{Height}$ 数组上建立 $\text{ST}$ 表，转换为 $\text{RMQ}$ 问题求解。
• 用平衡树维护每个新增后缀在已计算贡献的后缀中 按 $\text{rank}$ 的前驱后继即可。

$\large\text{Notes}$

• 后缀数组等字符串结构多采用增量式构造，支持头尾中单方向插入，不支持从中插入或删除。
• 处理增量式构造的原则：产生的影响和贡献尽量做到最少。