对一个字符串，怎么用后缀数组求出现i∈[1，n]次的子串的个数

利用height数组求解，首先我们要知道求L到R次的数量可以利用L次以上的数量减去R+1次以上的数量求得，那么这个题就转换为了求出现k次以上的字符串的个数。
首先k=1 特判，即 n-sa[i]-height[i]，即所有不相同子串。
k>1时，利用height数组，对每k-1个height数组求最小值，求出的结果记为 now ，若now>pre pre为上个k-1 heigh数组的最小值，则ans+=now-pre 之后将pre更新为now即可

后缀数组之求出现次数L到R次的字符串的个数_呜喵汪的博客-CSDN博客题目大意：给你一个字符串，求出现次数在L到R次之间的字符串的个数。解题思路：利用height数组求解，首先我们要知道求L到R次的数量可以利用L次以上的数量减去R+1次以上的数量求得，那么这个题就转换为了求出现k次以上的字符串的个数。首先k=1 特判，即 n-sa[i]-height[i]，即所有不相同子串。k>1时，利用height数组，对每k-1个heigh...

https://blog.csdn.net/f2935552941/article/details/82824916

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632