题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

题意：给定字符串S，求S的不同子串的总数量。 求出SA数组与Height数组，每个子串必然是某个后缀的前缀。令S的长度为N，则后缀SA[i]可以贡献出N-SA[i]个前缀。但其中有Height[i]个与之前的是重复的，因此要减去。 另外，在套模板的时候，处理的字符串S实际上比源字符串多一个结束标记，因此计算出的不同子串数量比答案要多N（N为S的长度，非源的长度，实际上就是源长度加1）。 SP

【题目描述】 给定一个字符串，计算其不同的子串个数。 【输入格式】 一行一个仅包含大写字母的字符串，长度<=50000 【输出格式】 一行一个正整数，即不同的子串个数。 【样例输入】 ABABA 【样例输出】 9 可以用后缀数组求出每个后缀的height，然后由于height为当前后缀与前边后缀最长公共前缀的最小值，所以当前后缀的不同子串数为该后缀长度减去该后缀的heght，最