记录编号	598092	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.441 s
提交时间	2025-01-05 10:53:45	内存使用	52.28 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 2e6+10,S = 26;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

int n;
string str;

vector<int>e[N];
struct SAM{
	int s[N][S];
	int len[N],link[N],cnt = 1,las = 1;
	int ins(int p,int x){
		if(s[p][x] && len[p] + 1 == len[s[p][x]])return s[p][x];
		int now = ++cnt,is = s[p][x];
		len[now] = len[p] + 1;
		while(!s[p][x])s[p][x] = now,p = link[p];
		if(!p)return link[now] = 1,now;
		int q = s[p][x];
		if(len[p] + 1 == len[q])return link[now] = q,now;
		int q2 = is ? now : ++cnt;
		link[q2] = link[q],len[q2] = len[p] + 1;
		for(int i = 0;i < S;i++)s[q2][i] = s[q][i];
		link[q] = q2;
		if(now != q2)link[now] = q2;
		while(s[p][x] == q)s[p][x] = q2,p = link[p];
		return now;
  	}
  	void add(string str){
  		las = 1;
  		for(char c : str)las = ins(las,c - 'A');
	}
  	void build(){
  		ll ans = 0;
  		for(int i = 2;i <= cnt;i++)ans += (ll)len[i] - len[link[i]];
  		printf("%lld\n",ans);
	}
}Tr;

int main(){
	freopen("subst1.in","r",stdin);
	freopen("subst1.out","w",stdout);
	cin>>str;
	Tr.add(str);
	Tr.build();

	return 0;

}