洛谷 P2408 不同子串个数 题解

一道很好的后缀数组和后缀自动机的练习题。本题解分成两个部分，分别讲解用后缀数组做和用后缀自动机做。

$1$.后缀数组

我们知道，后缀数组中的 $height$ 数组表示相邻两个前缀的最长相同前缀。一个长度为 $n$ 的字符串，有 $\frac{n\times (n-1)}{2}$ 个子串。那么我们只需要把 $height$ 数组求出来，在最后的答案中减去相同前缀数量的贡献，得到的答案就是不同字串的个数。

代码中是对于每次操作拆开求，实际上跟上面那个式子最后的答案相同。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24