Cod sursa(job #167612)
#include <stdio.h>
#define nmax 16384
#define base 62
#define primmax 2000005
#define infinit 2000005
#define KMAX 1
int N, K, ans;
char S[nmax];
int T[nmax], W[3][primmax], E[3][primmax], C[3][primmax], base2[3][nmax];
int mod[] = {2000003, 17, 928619};
int minim(int l, int r)
{
return l < r ? l : r;
}
void read()
{
freopen("substr.in", "r", stdin);
scanf("%d%d\n", &N, &K);
scanf("%s", &S);
}
void normalize()
{
int i, k;
for (i = 0; i < N; ++i)
{
if ('a' <= S[i] && S[i] <= 'z')
T[i] = S[i]-'a';
else if ('A'<=S[i] && S[i] <= 'Z')
T[i] = S[i]-'A'+26;
else
T[i] = S[i]-'0'+52;
}
for (k = 0; k < KMAX; ++k)
base2[k][0] = 1;
for (i = 1; i <= N; ++i)
for (k = 0; k < KMAX; ++k)
base2[k][i] = base * base2[k][i-1] % mod[k];
}
void bs(int l, int r)
{
int i, k, mini, min, v;
if (l > r)
return;
int L = (l+r)>>1;
for (k = 0; k < KMAX; ++k)
W[k][L-1] = 0;
for (i = 0; i < L; ++i)
for (k = 0; k < KMAX; ++k)
W[k][L-1] = (W[k][L-1] * base + T[i]) % mod[k];
for (k = 0; k < KMAX; ++k)
if (E[k][W[k][L-1]] != L)
{
C[k][W[k][L-1]] = 1;
E[k][W[k][L-1]] = L;
}
else
++C[k][W[k][L-1]];
mini = infinit;
for (k = 0; k < KMAX; ++k)
mini = minim(mini, C[k][W[k][L-1]]);
for (i = L; i < N; ++i)
{
for (k = 0; k < KMAX; ++k)
{
v = (W[k][i-1] * base + T[i] - T[i-L] * base2[k][L]) % mod[k];
while (v < 0) v += mod[k];
W[k][i] = v;
if (E[k][W[k][i]] != L)
{
C[k][W[k][i]] = 1;
E[k][W[k][i]] = L;
}
else
++C[k][W[k][i]];
}
min = infinit;
for (k = 0; k < KMAX; ++k)
min = minim(min, C[k][W[k][i]]);
if (min > mini)
mini = min;
}
if (mini >= K)
{
ans = L;
bs(L+1, r);
}
else
bs(l, L-1);
}
void solve()
{
normalize();
bs(0, N);
}
void write()
{
freopen("substr.out", "w", stdout);
printf("%d\n", ans);
}
int main()
{
read();
solve();
write();
return 0;
}