洛谷 P2408 不同子串个数（后缀数组）

不同子串个数

题目背景

因为 NOI 被虐傻了，蒟蒻的 YJQ 准备来学习一下字符串，于是它碰到了这样一道题：

题目描述

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

我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。

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

输入格式

第一行一个整数 $n$。

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

输出格式

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

样例 #1

样例输入 #1

5
aabaa
1
2

样例输出 #1

11
1

样例 #2

样例输入 #2

3
aba
1
2

样例输出 #2

5
1

提示

提示

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

数据规模与约定

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

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

  1、子串就是后缀的前缀，所以可以枚举每个后缀，计算前缀总数，再减掉重复。
  “前缀总数”其实就是子串个数，为 n * (n &#