先考虑没有修改操作，如何求不同的子串数量，这是后缀数组的经典应用。所有子串就是所有后缀的所有前缀。先将所有后缀按照字典序排序，然后求出\(height\)数组，从\(1\)循环到\(n\)，对于排名为\(i\)的后缀来说，新增的后缀个数就是\(\text{len}[i]-height[i]\)（前者表示排名为\(i\)的后缀的长度），因为排名为\(i\)的后缀的前缀，前\(height[i]\)个显然已经在前面统计过了，所以可能没统计过的就是长度至少为\(height[i]+1\)的，而这些前缀也一定没有统计过（否则，假设长度为\(j>height[i]\)的前缀在前面统计过，也就是说存在一个排名为\(k<i\)的后缀，其与\(i\)的\(\text{lcp}\)的长度至少为\(j\)，但是这个\(\text{lcp}\)的长度应该为\(\overset{i}{\underset{p=k+1}{\min}}height[p]\leq height[i]<j\)，矛盾）
再考虑有修改的操作，根据上面的分析，我们肯定是去维护所有后缀的总长度与当前\(height\)数组的总和；然而发现如果从后面直接插入会影响所有后缀（所有后缀都会增加一个字符），于是尝试将字符串翻转过来，然后看成从后往前依次添加字符，于是添加的字符就不会影响已经有了的后缀了；但是发现还要对\(height\)进行插入排序，于是将从后往前添加字符看成从前往后删除字符，这样子就可以每次只删除一个\(height\)了；但是还要维护删除的那个\(height\)位置前后两个\(height\)，于是用双向链表维护就好了（利用\(\text{lcp}(i-2,i)=\min(\text{lcp}(i-2,i-1),\text{lcp}(i-1,i))\)，时间复杂度为\(O(1)\)的）
标签：字符,前缀,lcp,后缀,text,魔咒,height,生成 From： https://www.cnblogs.com/dingxingdi/p/18375274