洛谷P2408题解：基于后缀数组的不同子串计数问题

不同子串个数

题目背景

因为 NOIP 比赛失利导致 YJQ 感到沮丧，
作为一位 stillbidding 的选手，
YJQ 决定系统地深入研究字符串处理技术。
从而遇到了一个关于字符串处理的挑战：

题目描述

给你一个长为 n 的字符串，求不同的子串的个数。

我们判定两个substring不同若且唯其它们的length不相等或两者length相同但至少有一位字符不同。

子串的定义：原字符串中连续的一段字符组成的字符串。

输入格式

第一行一个整数 n。

接下来一行 n 个字符表示给出的字符串。

输出格式

一行一个整数，表示不一样的子串个数。

样例 #1

样例输入 #1

    5
    aabaa

样例输出 #1

    11

样例 #2

样例输入 #2

    3
    aba

样例输出 #2

    5

提示

提示

请使用64位整数来进行输出。

数据规模与约定

对于 30\% 的数据，保证 n\le 1000。

对于 100\% 的数据，保证 1 \leq n \le 10^5，字符串中只有小写英文字母