DTKSUB - Chuỗi con xuất hiện K lần
Tác giả: ladpro98
Ngôn ngữ: Pascal
program DTKSUB;
uses math;
const base = 26;
hash = trunc(1e9)+13;
hash2 = hash*hash;
maxn=50004;
fi='';
var
h,pow,ph:array[0..maxn] of int64;
f:array[0..maxn] of longint;
inp:text;
res,n,k,i,l,r,m,oa:longint;
ok:boolean;
s:ansistring;
procedure sort(l,r:longint);
var p,t,i,j:longint;
begin
if l>=r then exit;
i:=l;j:=r;
p:=h[random(r-l+1)+l];
repeat
while h[i]<p do inc(i);
while h[j]>p do dec(j);
if i<=j then begin
if i<j then begin
t:=h[i];
h[i]:=h[j];
h[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;
begin
assign(inp,fi);reset(inp);
readln(inp,n,k);readln(inp,s);
if k=1 then begin
write(n);
halt;
end;
pow[0]:=1;oa:=ord('a');
for i:=1 to n do pow[i]:=(base*pow[i-1]) mod hash;
for i:=1 to n do ph[i]:=(base*ph[i-1]+ord(s[i])-oa) mod hash;
l:=1;r:=n;
while l<=r do begin
m:=(l+r) shr 1;
for i:=m to n do h[i]:=(ph[i] - pow[m]*ph[i-m] + hash2) mod hash;
sort(m,n);
f[m]:=1;ok:=false;
for i:=m+1 to n do begin
if h[i] = h[i-1] then f[i]:=f[i-1]+1
else f[i]:=1;
if f[i]>=k then begin
ok:=true;
break;
end;
end;
if (ok) then begin
l:=m+1;
res:=m;
end
else r:=m-1;
end;
write(res);
end.