GODI2015DAY2T3短信加密【后缀数组】

  • 内容
  • 评论
  • 相关

没错又是后缀数组,放心这是这一段时间内的最后一题了。。。


题目点击这里

总之还是后缀数组的题目,把题目翻译一下就变成了求一个字符串的不重叠相同子串的最大的(长度×数量)(好吧我语文不行。。。)


官方题解神秘失踪了。。。这里讲一下官方题解的做法。

30%可以暴力枚举子串找到在原串里的每一个位置,然后处理一下不重叠的情况:假设所有的位置已经找到,放在数组p里面,记录一个now变量,每次找到第一个大于等于now的p,就相当于找到下一个不重叠的子串,接下来把now变成p+l就可以。

100%的数据我们可以先弄出height数组,接下来枚举l,由于在sa数组里面有且只有相邻的一块后缀有着相同的前缀,所以height数组里面连续一块大于等于l的就是有相同的长度为l的前缀,接下来我们将这一块里面每一个后缀的位置找出来,用上面的方法贪心即可(因为要注意子串之间不能重叠)。


P.S:表示一开始看到k≥2就莫名其妙认为l也要大于等于2,然后就呵呵,肘子出的数据前5个点答案字符串长度都是1我也没啥好说的。。。


代码:

var
  s,ss,sss:ansistring;
  rank,trank,sa,tsa,sum,h:array[0..100000]of longint;
  i,j,k,n,m,p,l,max,now: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(s);
  n:=length(s);
  for i:=1 to n do inc(sum[ord(s[i])-96]);
  for i:=2 to 26 do inc(sum[i],sum[i-1]);
  for i:=n downto 1 do
  begin
    sa[sum[ord(s[i])-96]]:=i;
    dec(sum[ord(s[i])-96]);
  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 (sa[rank[i]-1]+j< =n) and (s[i+j]=s[sa[rank[i]-1]+j]) do inc(j);
    h[rank[i]]:=j;
    if j>0 then dec(j);
  end;
  max:=0;
  for l:=1 to n div 2 do
  begin
    i:=1;
    repeat
      while (h[i]<l ) and (i<n) do inc(i);
      if h[i]<l then break;
      fillchar(sum,sizeof(sum),0);
      inc(sum[sa[i-1]]);
      while (h[i]>=l) and (i< =n) do
      begin
        inc(sum[sa[i]]);
        inc(i);
      end;
      sss:=copy(s,sa[i-1],l);
      now:=0;
      k:=0;
      for j:=1 to n do
      if (sum[j]<>0) and (j>=now) then
      begin
        inc(k);
        now:=j+l;
      end;
      if (max< =l*k) and (k>1) then
      begin
        if (max=l*k) and (sss<ss ) or (ss='') then ss:=sss;
        if max<l*k then ss:=sss;
        max:=l*k;
      end;
    until i=n;
  end;
  if max=0 then writeln(-1) else
  begin
    writeln(max);
    writeln(ss);
  end;
end.

评论

0条评论

发表评论

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

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