【题意】
给定一个长度为n的整数序列,求其中至少出现k次的子序列长度最长为多长
【输入】
第一行n和k
接下来n个数字描述序列
【输出】
一个数字,表示至少出现过k次的子序列最长长度
也是09年论文《后缀数组——处理字符串的有力工具》上的例题
不过不同之处是二分答案之时,判断方式是一组中是否有k个后缀
program poj3261; var n,i,j,k,s,e,mid,min,max,less:longint; dl,root,rank,sa,height,total,now,change,keep:array [-1..20001] of longint; ok:boolean; procedure qsort (s,e:longint); var i,j,k,o:longint; begin if s>=e then exit; i:=s; j:=e; k:=dl[(s+e) div 2]; while i<=j do begin while root[dl[i]]<root[k] do inc(i); while root[dl[j]]>root[k] do dec(j); if i>j then break; o:=dl[i]; dl[i]:=dl[j]; dl[j]:=o; inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; begin read(n,less); for i:=1 to n do read(root[i]); for i:=1 to n do dl[i]:=i; qsort(1,n); k:=1; for i:=1 to n do if root[dl[i]]=root[dl[k]] then rank[dl[i]]:=k else begin k:=i; rank[dl[i]]:=k; end; k:=0; while 1 shl k<n do begin for i:=1 to n do if i+(1 shl k)>n then change[i]:=0 else change[i]:=rank[i+(1 shl k)]; fillchar(total,sizeof(total),0); for i:=1 to n do inc(total[change[i]]); for i:=1 to n do total[i]:=total[i-1]+total[i]; for i:=1 to n do begin dl[total[change[i]-1]+1]:=i; inc(total[change[i]-1]); end; fillchar(total,sizeof(total),0); ok:=true; for i:=1 to n do begin inc(total[rank[i]]); if total[rank[i]]=2 then ok:=false; end; if ok then break; for i:=2 to n do total[i]:=total[i]+total[i-1]; fillchar(now,sizeof(now),0); fillchar(keep,sizeof(keep),0); for i:=1 to n do begin if change[dl[i]]<>now[rank[dl[i]]] then begin now[rank[dl[i]]]:=change[dl[i]]; total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]]; keep[rank[dl[i]]]:=0; end; inc(keep[rank[dl[i]]]); rank[dl[i]]:=total[rank[dl[i]]-1]+1; end; inc(k); end; for i:=1 to n do sa[rank[i]]:=i; fillchar(height,sizeof(height),0); for i:=1 to n do begin if rank[i]=1 then continue; k:=height[rank[i-1]]-1; if k<0 then k:=0; while (sa[rank[i]-1]+k<=n)and(i+k<=n)and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k); height[rank[i]]:=k; end; s:=1; e:=n; while s<>e do begin mid:=s+e-(s+e) div 2; ok:=false; k:=0; for i:=2 to n do if height[i]>=mid then begin inc(k); if k>=less then begin ok:=true; break; end; end else k:=1; if ok then s:=mid else e:=mid - 1; end; writeln(s); end.