【文文殿下】洛谷P2408 不同子串个数

题目链接https://www.luogu.org/problemnew/show/P2408

SAM裸题，大力求就行了

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn = 2e5+20;
int par[maxn],mx[maxn],tr[maxn][26];
int cnt=1,last=1;
void extend(int x) {
	int np = ++cnt,p=last;
	mx[np]=mx[p]+1;
	last=np;
	while(p&&!tr[p][x]) tr[p][x]=np,p=par[p];
	if(!p) par[np]=1;
	else {
		int q = tr[p][x];
		if(mx[q]==mx[p]+1) {
			par[np]=q;
		}
		else {
			int nq = ++cnt;
			mx[nq]=mx[p]+1;
			memcpy(tr[nq],tr[q],sizeof tr[q]);
			par[nq]=par[q];par[q]=par[np]=nq;
			while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p];
		}
	}
	return;
}
int n;
char A[100010];
int main() {
	scanf("%d",&n);
	scanf("%s",A+1);
	for(int i =1;i<=n;++i) {
		extend(A[i]-'a');
	}
	ll ans = 0;
	for(int i = 1;i<=cnt;++i) ans+=(mx[i]-mx[par[i]]);
	printf("%lld
",ans);
	return 0;
}