都LCP了很显然是要用到后缀数组的
显然前面的那个东西是可以直接算出来的
关键在于LCP的和怎么快速的计算
不难想到穷举height[i],然后判断这个height[i]可能成为多少对后缀的LCP
考虑到LCP(i,j)=min(height[rank[i]+1~rank[j]]) 假定rank[i]<rank[j];
假设height[l]是左边第一个小于height[i]的，height[r]是右边第一个小于height[i]的
则height[i]是(i-l)(r-i)对后缀的LCP
但这样有一个问题，相同height可能会被重复计算
为了避免重复，我们定义height[r]是右边第一个不大于height[i]的
这样就有两种方法来实现
第一种是二分+rmq，但不幸的是我竟然写超时，而且我觉得容易出错
第二种是利用单调队列，我们把height[i]对应的l,r定义为左右边界，记为l[i],r[i];
计算左边界和右边界是相似的，这里我们讨论左边界
假如height[j]<=height[k] (j>k) 那么对于之后的height[i],
要么能延伸到k之前（height[i]<=height[j]),要么只能左边界就是j(height[i]>height[j])，不用比较height[k]
显然我们要维护一个单调不降的队列就行了
最后计算的时候注意用int64
var rank,sa,y,q,x,sum,h,l,r:array[..] of longint;
s:ansistring;
i,n,m,p,j,t:longint;
ans,z:int64; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure suffix;
var i,j,p:longint;
begin
for i:= to n do
begin
y[i]:=ord(s[i]);
inc(sum[y[i]]);
end;
m:=;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[y[i]]]:=i;
dec(sum[y[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if y[sa[i]]<>y[sa[i-]] then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
fillchar(sum,sizeof(sum),);
y:=rank;
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i]>j then
begin
inc(p);
x[p]:=sa[i]-j;
end; for i:= to n do
begin
rank[i]:=y[x[i]];
inc(sum[rank[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[rank[i]]]:=x[i];
dec(sum[rank[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (y[sa[i]]<>y[sa[i-]]) or (y[sa[i]+j]<>y[sa[i-]+j]) then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=j shl ;
end;
h[]:=;
p:=;
for i:= to n do
begin
if rank[i]= then continue;
j:=sa[rank[i]-];
while (i+p<=n) and (j+p<=n) and (s[i+p]=s[j+p]) do inc(p);
h[rank[i]]:=p;
if p> then dec(p);
end;
end; function calc(i,x,y:int64):int64;
begin
exit(*h[i]*(i-x)*(y-i));
end; begin
readln(s);
n:=length(s);
suffix;
z:=n;
ans:=(z+)*z div *(z-);
t:=;
for i:= to n do
begin
while (t>) and (h[q[t]]>=h[i]) do dec(t);
if t= then l[i]:=
else l[i]:=q[t];
inc(t);
q[t]:=i;
end;
t:=;
for i:=n downto do
begin
while (t>) and (h[q[t]]>h[i]) do dec(t); //注意右边界是第一个不大于的height，防止重复
if t= then r[i]:=n+
else r[i]:=q[t];
inc(t);
q[t]:=i;
end;
for i:= to n do
ans:=ans-calc(i,l[i],r[i]);
writeln(ans);
end.