BZOJ3172单词【后缀数组】
后缀数组三连发~
题目:某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。
注意题目所说的文章是把读入的每一个单词中间加一个空格隔开的一个长字符串,还有题目所说的单词长度不超过10^6是指单词的总长度,不然空间不够。。
后缀数组的性质之一就是排序后有相同前缀的后缀是连在一起的,所以我们可以弄出整篇文章,用后缀数组处理后,找到所有前缀包含每个单词的后缀数量就是答案。首先需要记录每个单词在文章中的开头位置,还有每个单词的长度,接下来我们用rank数组找到这个单词开头的后缀在SA中的位置,然后找到所有连着的、height小于单词长度的后缀就可以了。(注意要开ansistring。。。还有调试完要把改小的数组改回去。。。)
var s,ss:ansistring; rank,trank,sa,tsa,sum,h,pos,l:array[0..2000000]of longint; i,j,k,n,m,p:longint; procedure sort(j:longint); var i:longint; begin fillchar(sum,sizeof(sum),0); for i:=1 to n do inc(sum[rank[i+j]]); for i:=1 to n do inc(sum[i],sum[i-1]); for i:=n downto 1 do begin tsa[sum[rank[i+j]]]:=i; dec(sum[rank[i+j]]); end; fillchar(sum,sizeof(sum),0); for i:=1 to n do inc(sum[rank[i]]); for i:=2 to n do inc(sum[i],sum[i-1]); for i:=n downto 1 do begin sa[sum[rank[tsa[i]]]]:=tsa[i]; dec(sum[rank[tsa[i]]]); end; end; begin readln(m); pos[1]:=1; for i:=1 to m do begin readln(ss); s:=s+ss+' '; pos[i+1]:=pos[i]+length(ss)+1; l[i]:=length(ss); end; n:=length(s); for i:=1 to n do inc(sum[ord(s[i])]); for i:=1 to 255 do inc(sum[i],sum[i-1]); for i:=n downto 1 do begin sa[sum[ord(s[i])]]:=i; dec(sum[ord(s[i])]); end; rank[sa[1]]:=1; p:=1; for i:=2 to n do begin if s[sa[i]]<>s[sa[i-1]] then inc(p); rank[sa[i]]:=p; end; j:=1; while j<n do begin sort(j); trank[sa[1]]:=1; p:=1; for i:=2 to n do begin if (rank[sa[i]]<>rank[sa[i-1]]) or (rank[sa[i]+j]<>rank[sa[i-1]+j]) then inc(p); trank[sa[i]]:=p; end; for i:=1 to n do rank[i]:=trank[i]; j:=j*2; end; j:=0; for i:=1 to n do begin if rank[i]=1 then continue; while s[i+j]=s[sa[rank[i]-1]+j] do inc(j); h[rank[i]]:=j; if j>0 then dec(j); end; for i:=1 to m do begin j:=rank[pos[i]]; k:=j+1; while h[j]>=l[i] do dec(j); while h[k]>=l[i] do inc(k); writeln(k-j); end; end.</n>
发表回复