BZOJ1031字符加密Cipher【后缀数组】
后缀数组的简单题。
题目:
喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:
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.
发表评论