Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

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.

Code mẫu của RR

//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.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 200005
#define maxa 30

int n, m, from, to, nc, a[maxn], p[maxn], c[maxn], pn[maxn], cn[maxn], cnt[maxn], lcp[maxn];
char s[maxn];

void suffix_array() {
    Rep(i, n) a[i] = s[i] - 'a' + 1;
    a[n++] = 0;

    ms(cnt, 0);
    Rep(i, n) ++cnt[a[i]];
    For(i, 1, maxa - 1) cnt[i] += cnt[i - 1];
    Repd(i, n) p[--cnt[a[i]]] = i;

    nc = 1; c[p[0]] = 0;
    For(i, 1, n - 1) {
        if (a[p[i]] > a[p[i - 1]]) ++nc;
        c[p[i]] = nc - 1;
    }

    for (int h = 1; h < n; h <<= 1) {
        Rep(i, n) {
            pn[i] = p[i] - h;
            if (pn[i] < 0) pn[i] += n;
        }

        ms(cnt, 0);
        Rep(i, n) ++cnt[c[pn[i]]];
        For(i, 1, nc - 1) cnt[i] += cnt[i - 1];
        Repd(i, n) p[--cnt[c[pn[i]]]] = pn[i];

        nc = 1; cn[p[0]] = 0;
        For(i, 1, n - 1) {
            int x = (p[i] + h) % n, y = (p[i - 1] + h) % n;
            if (c[p[i]] > c[p[i - 1]] || c[x] > c[y]) ++nc;
            cn[p[i]] = nc - 1;
        }
        Rep(i, n) c[i] = cn[i];
    }

    int h = 0;
    Rep(i, n) {
        if (c[i] > 0) {
            int j = p[c[i] - 1];
            while (a[i + h] == a[j + h]) ++h;
            lcp[c[i]] = h;
            if (h > 0) --h;
        }
    }

}

bool check(int d){
    if(d > n) return false;
    int run = 1, MAX = 0;
    For(i, 1, n - 1){
        if(lcp[i] < d){
            run = 1;
        }
        else run++;
        MAX = max(run, MAX);
    }
    return MAX >= m;
}

int main(){
//    freopen("in.txt", "r", stdin);
    cin >> n >> m;
    scanf("%s", s);
    suffix_array();
    int l = 1, r = n, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)){
            l = mid + 1;
        }
        else r = mid;
    }

    cout << l - 1 << endl;

    return 0;
}

Code mẫu của skyvn97

#include<deque>
#include<iostream>
#include<string>
#include<vector>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define MASK(i) (1<<(i))
#define tget(i) ((t[(i)/8]&MASK((i)%8))?1:0)
#define tset(i,b) t[(i)/8]=(b)?(t[(i)/8]|MASK((i)%8)):(t[(i)/8]&(~MASK((i)%8)))
#define chr(i) ((cs==sizeof(int))?((int *)s)[i]:((unc *)s)[i])
#define isLMS(i) ((i)>0 && tget(i) && !tget((i)-1))
using namespace std;
typedef unsigned char unc;
class SuffixArray {
    private:
    int *sa,*lcp,*rank,n;
    unc *s;
    void getbuckets(unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
        FOR(i,0,k) bkt[i]=0;
        REP(i,n) bkt[chr(i)]++;
        int sum=0;
        FOR(i,0,k) {
            sum+=bkt[i];
            bkt[i]=end?sum:sum-bkt[i];
        }
    }
    void inducesal(vector<unc> &t,int sa[],unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
        getbuckets(s,bkt,n,k,cs,end);
        REP(i,n) {
            int j=sa[i]-1;
            if (j>=0 && !tget(j)) sa[bkt[chr(j)]++]=j;
        }
    }
    void inducesas(vector<unc> &t,int sa[],unc s[],vector<int> &bkt,int n,int k,int cs,bool end) {
        getbuckets(s,bkt,n,k,cs,end);
        FORD(i,n-1,0) {
            int j=sa[i]-1;
            if (j>=0 && tget(j)) sa[--bkt[chr(j)]]=j;
        }
    }
    void build(unc s[],int sa[],int n,int k,int cs) {
        int j;
        vector<unc> t=vector<unc>(n/8+1,0);
        tset(n-2,0);
        tset(n-1,1);
        FORD(i,n-3,0) tset(i,(chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)))?1:0);
        vector<int> bkt=vector<int>(k+1,0);
        getbuckets(s,bkt,n,k,cs,true);
        REP(i,n) sa[i]=-1;
        REP(i,n) if (isLMS(i)) sa[--bkt[chr(i)]]=i;
        inducesal(t,sa,s,bkt,n,k,cs,false);
        inducesas(t,sa,s,bkt,n,k,cs,true);
        bkt.clear();
        int n1=0;
        REP(i,n) if (isLMS(sa[i])) sa[n1++]=sa[i];
        FOR(i,n1,n-1) sa[i]=-1;
        int name=0;
        int prev=-1;
        REP(i,n1) {
            int pos=sa[i];
            bool diff=false;
            REP(d,n) {
                if (prev<0 || chr(prev+d)!=chr(pos+d) || tget(prev+d)!=tget(pos+d)) {
                    diff=true;
                    break;
                }
                else if (d>0 && (isLMS(prev+d) || isLMS(pos+d))) break;
            }
            if (diff) {
                name++;
                prev=pos;
            }
            sa[n1+pos/2]=name-1;
        }
        j=n-1;
        FORD(i,n-1,n1) if (sa[i]>=0) sa[j--]=sa[i];
        int *sa1=sa;
        int *s1=sa+n-n1;
        if (name<n1) build((unc *)s1,sa1,n1,name-1,sizeof(int));
        else REP(i,n1) sa1[s1[i]]=i;
        bkt.assign(k+1,0);
        getbuckets(s,bkt,n,k,cs,true);
        j=0;
        REP(i,n) if (isLMS(i)) s1[j++]=i;
        REP(i,n1) sa1[i]=s1[sa1[i]];
        FOR(i,n1,n-1) sa[i]=-1;
        FORD(i,n1-1,0) {
            j=sa[i];
            sa[i]=-1;
            sa[--bkt[chr(j)]]=j;
        }
        inducesal(t,sa,s,bkt,n,k,cs,false);
        inducesas(t,sa,s,bkt,n,k,cs,true);
        bkt.clear();
        t.clear();
    }
    void calc_lcp(void) {
        FOR(i,1,n) rank[sa[i]]=i;
        int h=0;
        REP(i,n) if (rank[i]<n) {
            int j=sa[rank[i]+1];
            while (s[i+h]==s[j+h]) h++;
            lcp[rank[i]]=h;
            if (h>0) h--;
        }
    }
    void count(int k) {
        if (k==0) {
            cout << n;
            return;
        }
        int res=0;
        deque<int> dq;
        while (!dq.empty()) dq.pop_back();
        FOR(i,1,n-1) {
            while (!dq.empty() && lcp[i]<=lcp[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if (i>=k) {
                while (!dq.empty() && dq.front()<=i-k) dq.pop_front();
                res=max(res,lcp[dq.front()]);
            }
        }
        cout << res;
    }
    public:
    SuffixArray() {
        n=0;
        sa=NULL;lcp=NULL;rank=NULL;
        s=NULL;
    }
    SuffixArray(string &ss,int k) {
        n=ss.size();
        sa=new int[n+7];
        lcp=new int[n+7];
        rank=new int[n+7];
        s=(unc *)ss.c_str();
        build(s,sa,n+1,256,sizeof(char));
        calc_lcp();
        //FOR(i,1,n) printf("%d %d\n",sa[i],lcp[i]);
        count(k-1);
    }
};
int main(void) {
    ios::sync_with_stdio(false);
    int n,k;
    string s;
    cin >> n >> k >> s;
    SuffixArray SA=SuffixArray(s,k);
    return 0;
}