fork(9) download
copy 
  1. program DTKSUB;
  2. const   maxN=trunc(5e4)+10;
  3.         base1=2147483648;
  4.         base=2147483647;
  5. var     n,k,ans: longint;
  6.         pow,hash,a: array[0..maxN] of longint;
  7.         s: ansistring;
  8. procedure sort(l,h: longint);
  9.  var    i,j,x,tm: longint;
  10.  begin
  11.         i:=l;
  12.         j:=h;
  13.         x:=a[random(h-l+1)+l];
  14.         repeat
  15.                 while a[i]<x do inc(i);
  16.                 while a[j]>x do dec(j);
  17.                 if i<=j then
  18.                  begin
  19.                         tm:=a[i];
  20.                         a[i]:=a[j];
  21.                         a[j]:=tm;
  22.                         inc(i); dec(j);
  23.                  end;
  24.         until i>j;
  25.         if i<h then sort(i,h);
  26.         if j>l then sort(l,j);
  27.  end;
  28. function get(i,j: longint): longint ;
  29.  begin
  30.         exit( (hash[j]-int64(hash[i-1])*pow[j-i+1]+ base1*base1) and base );
  31.  end;
  32. function kt(n: longint): boolean;
  33.  var    i,j: longint;
  34.  begin
  35.         i:=1;
  36.         while i<=n-k+1 do
  37.          begin
  38.                 j:=i;
  39.                 while (a[j]=a[j+1]) and (j<n) do inc(j);
  40.                 if j-i+1>=k then exit(true);
  41.                 i:=j+1;
  42.          end;
  43.         exit(false);
  44.  end;
  45. procedure main;
  46.  var    i,l,r,m: longint;
  47.  begin
  48.         readln(n,k);
  49.         readln(s);
  50.         pow[0]:=1;
  51.         for i:=1 to n do pow[i]:=(int64(pow[i-1])* 26) and base;
  52.         for i:=1 to n do hash[i]:=(int64(hash[i-1])*26+ord(s[i])-97) and base;
  53.         l:=1; r:=n-k+1;
  54.         while l<=r do
  55.          begin
  56.                 m:=(l+r) shr 1;
  57.                 for i:=1 to n-m+1 do
  58.                         a[i]:=get(i,i+m-1);
  59.                 sort(1,n-m+1);
  60.                 if kt(n-m+1) then
  61.                  begin
  62.                         ans:=m;
  63.                         l:=m+1;
  64.                  end
  65.                 else    r:=m-1;
  66.          end;
  67.         write(ans);
  68.  end;
  69. BEGIN
  70.         main;
  71. END.
Success #stdin #stdout 0s 860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/biRasf
problem DTKSUB, based on SPOJ submission 14658684 (PAS fpc), 2015-07-13 11:06:50
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!