C++(g++ 7.5.0) 解法, 执行用时: 385ms, 内存消耗: 238776K, 提交时间: 2023-04-18 23:16:43

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10, M = N << 1;
int fa[M], len[M], tot = 1, np = 1;
int ch[M][26];
vector<int> g[M];
char s[N];
ll sum = 0;

void extend(int c)
{
	int p = np; np = ++tot;
	len[np] = len[p] + 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[np] = q;
		}
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
	sum += (len[np] - len[fa[np]]);
}

signed main()
{
	scanf("%s", s);
	for (int i = 0; s[i]; ++i) {
		extend(s[i] - 'a');
	}
	printf("%lld\n", sum);

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1656ms, 内存消耗: 25064K, 提交时间: 2023-01-05 20:38:36

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
typedef long long LL;
int rk[2*N],sa[2*N],oldrk[2*N];
LL ht[2*N];
int main()
{
	string s;
	cin>>s;
	LL n=s.length();
	s="?"+s;
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
	for(int w=1;w<n;w<<=1)
	{
		sort(sa+1,sa+n+1,[&](int a,int b){
			return rk[a]==rk[b]?rk[a+w]<rk[b+w]:rk[a]<rk[b];
			});
		memcpy(oldrk+1,rk+1,sizeof rk);
		for(int i=1,p=0;i<=n;i++)
		{
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])
			{
				rk[sa[i]]=p;
			}
			else rk[sa[i]]=++p;
		}
	}
	for(int i=1,h=0;i<=n;i++)
	{
		if(rk[i]==0)continue;
		if(h)h--;
		int j=sa[rk[i]-1];
		while(s[i+h]==s[j+h])h++;
		ht[rk[i]]=h;
	}
	LL ans=(1+n)*n/2;
	for(int i=1;i<=n;i++)
	{
		ans=ans-ht[i];
	}
	cout<<ans<<endl;
}