spoj DISUBSTR – Distinct Substrings (统计字串个数,后缀数组)

题目链接

题意:给出一个字符串,问所有不同的字串的个数。

思路:直接求比较困难。我们考虑,假如组成字符串的所有字符都不相同,那么就没有相同的字串,假设字符串的长度为n,那么长度为1的子串有n个,为2的有n-1个。。。为n的有1个,一共就是n*(n+1)/2个。。但是实际上会有重复的。。。

我们再次考虑这张图。Selection_004

先找一个字符重复的个数,对应height[i]数组就是找height[i]大于等于1个的个数(因为x个height代表了x+1个后缀,保留1个,重复了x个,所以重复的个数恰好和符合条件的height数组对应

接着找大于等于2的个数,大于等于3的个数…

最后再把所有答案累加起来,就是总共重复的次数。

然后按照我推出的这个结论,试着写了一发。。。1A蛤蛤蛤。。。

能想到这里大概是因为之前的题目让我得出了,“height数组是个小妖精”的结论,所以入手就先观察了一下height数组。。。

具体的实现呢,就是先统计height[i]中每个值出现的次数,然后做一个后缀和,最后累加。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz