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.

Download