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>

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据