一道很好的后缀数组和后缀自动机的练习题。本题解分成两个部分,分别讲解用后缀数组做和用后缀自动机做。
我们知道,后缀数组中的 h e i g h t height height 数组表示相邻两个前缀的最长相同前缀。一个长度为 n n n 的字符串,有 n × ( n − 1 ) 2 \frac{n \times (n-1)}{2} 2n×(n−1) 个子串。那么我们只需要把 h e i g h t height 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