1. 首页
  2. Let's OI!
  3. 正文

BZOJ1031字符加密Cipher【后缀数组】

  • 内容
  • 评论
  • 相关

后缀数组的简单题。

题目：
喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：
null
JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

要处理所有长度为n的子串，一个比较好的办法就是把原串复制一次，比如说原来的JSOI07变成JSOI07JSOI07，这样所有长度大于n的后缀的前面n位都是我们需要的了，而第n位以后的东西不会对答案产生影响，所以我们只要把长度大于n的后缀弄出来，就可以了。（老是忘了开ansistring）

var
  s:ansistring;
  rank,trank,sa,tsa,sum,h:array[0..200000]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(s);
  s:=s+s;
  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
  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;
  for i:=1 to n do
  begin
    if sa[i]<=n div 2 then write(s[sa[i]+n div 2-1]);
  end;
  writeln;
end.

评论

0条评论

发表评论

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

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