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.
发表回复