DTKSUB - Chuỗi con xuất hiện K lần
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 50111;
hashkey = 1000003;
var
f1,f2 : text;
n,k : longint;
count : array[0..hashkey] of longint;
sum,lt,a : array[0..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
c:char;
begin
readln(f1,n,k);
for i:=1 to n do
begin
read(f1,c);
a[i]:=ord(c)-ord('a');
end;
end;
function check(val:longint):boolean;
var
i,j,tmp:longint;
begin
fillchar(count,sizeof(count),0);
for i:=1 to n-val+1 do
begin
j:=i+val-1;
tmp:=(int64(lt[n-i])*(sum[j]-sum[i-1]+hashkey)) mod hashkey;
inc(count[tmp]);
if count[tmp]>=k then exit(true);
end;
exit(false);
end;
procedure solve;
var
i,l,r,mid,res:longint;
begin
lt[0]:=1;
for i:=1 to n do
lt[i]:=(lt[i-1]*26) mod hashkey;
for i:=1 to n do
sum[i]:=(sum[i-1]+a[i]*lt[i-1]) mod hashkey;
l:=1; r:=n; res:=0;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid) then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
writeln(f2,res);
end;
begin
openF;
inp;
solve;
closeF;
end.