瓶颈在哪儿？ 你会发现每往后添加一个字符，整个 sa 数组只会插入一个数，要维护不难 但是 height 会无规律变化，这就导致无法高效维护 怎么办呢？ 倒置字符串 我们将整个字符串倒置过来 显然本质不同的子串个数不会变化 而每往前添加一个字符串， height 的变化是 O(1) 的 那么，问题就变得简单很多了 具体实现请看代码注释