给你一个长度不超过 100000 的字符串（小写字母）

求不同子串的个数

题解：后缀数组

后缀数组的原理

后缀数组的模板和应用

每个子串一定是某个后缀的前缀，及等价于求后缀之间不相同前缀的个数

每个后缀可以提供 （n+1-sa[i]）个子串，其中有height[i]个重复

/*
Algorithm: 后缀数组求 不同子串的个数 
Author: anthony1314
Creat Time:2019.4.18 
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 1e9 + 7
#define line printf("--------------");
#define maxn 100005
using namespace std;
int n,m,sa[maxn],rk[maxn],tp[maxn],tax[maxn],p;
int height[maxn],T;
char s[maxn];
long long ans;
void Qsort() {
	for(int i=0; i<=m; i++) {
		tax[i]=0;
	}
	for(int i=1; i<=n; i++) {
		tax[rk[i]]++;
	}
	for(int i=1; i<=m; i++) {
		tax[i]+=tax[i-1];
	}
	for(int i=n; i>=1; i--) {
		sa[ tax[rk[tp[i]]]-- ]=tp[i];
	}
}
void get_height(int n) {
	int k=0,j;
	for(int i=1; i<=n; i++) {
		j=sa[rk[i]-1];
		if(k) {
			k--;
		}
		while(s[j+k]==s[i+k]) {
			k++;
		}
		height[rk[i]]=k;
	}
}
int main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1; i<=n; i++) {
		rk[i]=s[i]-'a';
		tp[i]=i;
	}
	m=105;
	Qsort();
	for(int ws=1,p=0; p<n; m=p,ws<<=1) {
		p=0;
		for(int i=1; i<=ws; i++) {
			tp[++p]=n-ws+i;
		}
		for(int i=1; i<=n; i++) {
			if(sa[i]>ws)tp[++p]=sa[i]-ws;
		}
		Qsort();
		swap(tp,rk);
		rk[sa[1]]=p=1;
		for(int i=2; i<=n; i++) {
			rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+ws]==tp[sa[i]+ws])?p:++p;
		}
	}
	get_height(n);
	ans=0;
	for(int i=1; i<=n; i++) {
		ans+=n+1-sa[i]-height[i];
	}
	printf("%lld\n",ans);
	return 0;
}