求不相同子串个数 该问题等价于求所有后缀间不相同前缀的个数..也就是对于每个后缀suffix(sa[i]),将贡献出n-sa[i]+1个,但同时,要减去那些重复的,即为height[i],故答案为n-sa[i]+1-height[i]的累计。
const maxn=1419; var x,y,rank,sa,h,c:array[0..maxn] of longint; s:ansistring; t,q,n:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end; procedure make; var i,j,p,tot:longint; begin p:=1; while p<n do begin fillchar(c,sizeof(c),0); for i:= 1 to n-p do y[i]:=rank[i+p]; for i:= n-p+1 to n do y[i]:=0; for i:= 1 to n do inc(c[y[i]]); for i:= 1 to n do inc(c[i],c[i-1]); for i:= 1 to n do begin sa[c[y[i]]]:=i; dec(c[y[i]]); end; fillchar(c,sizeof(c),0); for i:= 1 to n do x[i]:=rank[i]; for i:= 1 to n do inc(c[x[i]]); for i:= 1 to n do inc(c[i],c[i-1]); for i:= n downto 1 do begin y[sa[i]]:=c[x[sa[i]]]; dec(c[x[sa[i]]]); end; for i:= 1 to n do sa[y[i]]:=i; tot:=1; rank[sa[1]]:=1; for i:= 2 to n do begin if (x[sa[i]]<>x[sa[i-1]]) or (x[sa[i]+p]<>x[sa[i-1]+p]) then inc(tot); rank[sa[i]]:=tot; end; p:=p<<1; end; end; procedure makeht; var i,j,p:longint; begin h[1]:=0; p:=0; for i:= 1 to n do begin p:=max(p-1,0); if rank[i]=1 then continue; j:=sa[rank[i]-1]; while (i+p<=n) and (j+p<=n) and (s[i+p]=s[j+p]) do inc(p); h[rank[i]]:=p; end; end; procedure init; var i,j,tot:longint; ch:char; begin readln(s); n:=length(s); for i:= 1 to n do x[i]:=ord(s[i]); fillchar(c,sizeof(c),0); for i:= 1 to n do inc(c[x[i]]); for i:= 1 to 180 do inc(c[i],c[i-1]); for i:= 1 to n do begin sa[c[x[i]]]:=i; dec(c[x[i]]); end; rank[sa[1]]:=1; tot:=1; for i:= 2 to n do begin if x[sa[i]]<>x[sa[i-1]] then inc(tot); rank[sa[i]]:=tot; end; make; makeht; end; procedure solve; var ans,i:longint; begin ans:=0; for i:= 1 to n do inc(ans,n-sa[i]+1-h[i]); writeln(ans); end; Begin readln(t); for q:= 1 to t do begin init; solve; end; End.
【SPOJ694】Distinct Substrings (SA)
原文:http://www.cnblogs.com/EC-Ecstasy/p/4168185.html