后缀数组

const maxn=200000;
var n,tot:longint;
    sa,rank,height,ws,r:array[0..maxn+10]of longint;
    x:array[0..1,0..maxn+10]of longint;

procedure init;
var s:string;
    i,j,k:longint;
begin
  fillchar(r,sizeof(r),0);
  readln(n);
  i:=n;tot:=0;
  while i>0 do
   begin
     readln(s);
     dec(i,80);
     j:=length(s);
     for k:=1 to j do
      begin
        inc(tot);
        r[tot]:=ord(s[k])-ord('a')+1;
      end;
   end;
end;

procedure calsa(n,m:longint);
var i,j,p,w:longint;
begin
  fillchar(ws,sizeof(ws),0);
  w:=0;p:=0;j:=1;
  for i:=1 to n do inc(ws[r[i]]);
  for i:=1 to m do inc(ws[i],ws[i-1]);
  for i:=n downto 1 do begin
  dec(ws[r[i]]);sa[ws[r[i]]]:=i;end;
  for i:=1 to n do x[w][i]:=r[i];
  while m<n do
   begin
     for i:=n-j+1 to n do begin
     inc(p);x[1-w][p]:=i;end;
     for i:=0 to n-1 do
      if sa[i]>j then begin
      inc(p);x[1-w][p]:=sa[i]-j;end;
     fillchar(ws,sizeof(ws),0);
     for i:=1 to n do inc(ws[x[w][x[1-w][i]]]);
     for i:=1 to m do inc(ws[i],ws[i-1]);
     for i:=n downto 1 do begin
     dec(ws[x[w][x[1-w][i]]]);
     sa[ws[x[w][x[1-w][i]]]]:=x[1-w][i];end;
     p:=1;w:=w xor 1;x[w][sa[0]]:=0;
     for i:=1 to n-1 do
      if (x[1-w][sa[i]]=x[1-w][sa[i-1]])and
         (x[1-w][sa[i]+j]=x[1-w][sa[i-1]+j]) then
           x[w][sa[i]]:=x[w][sa[i-1]] 
         else begin x[w][sa[i]]:=x[w][sa[i-1]]+1;inc(p);end;
     m:=p;j:=j shl 1;p:=0;
   end;
end;

procedure calheight(n:longint);
var i,j,k:longint;
begin
  for i:=1 to n do
    rank[sa[i]]:=i;
  k:=0;
  for i:=1 to n do
   begin
     if k<>0 then dec(k);
     j:=sa[rank[i]-1];
     while r[i+k]=r[j+k] do inc(k);
     height[rank[i]]:=k;
   end;
end;

procedure main;
var ans:int64;i,j:longint;
begin
  ans:=0;
  for i:=1 to n do
   ans:=ans+n-sa[i]+1-height[i];
  write(ans);
end;

begin
  init;
  calsa(n+1,ord('z')-ord('a')+1);
  calheight(n);
  main;
end.