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.

Download