Cod sursa(job #953229)
#include <cstdio>
#include <cstdlib>
#include <map>
#include <algorithm>
using namespace std;
#define PI pair<int, int>
#define mp make_pair
#define Mod1 100021
#define Mod2 100007
#define Nmax 16400
int N, K, C1[Nmax], C2[Nmax], P1[Nmax], P2[Nmax];
char S[Nmax];
map<PI, int> Hash;
bool Check(int L)
{
Hash.clear();
for(int i = 1; i + L - 1 <= N; ++ i)
{
int SubC1 = (C1[i + L - 1] - C1[i - 1] * P1[L]) % Mod1;
while(SubC1 < 0) SubC1 += Mod1;
int SubC2 = (C2[i + L - 1] - C2[i - 1] * P2[L]) % Mod2;
while(SubC2 < 0) SubC2 += Mod2;
Hash[mp(SubC1, SubC2)] ++;
}
for(map<PI, int> :: iterator it = Hash.begin(); it != Hash.end(); ++ it)
if(it -> second >= K)
return 1;
return 0;
}
int main()
{
freopen("substr.in", "r", stdin);
freopen("substr.out", "w", stdout);
int i;
scanf("%i %i\n", &N, &K);
gets(S + 1);
P1[0] = P2[0] = 1;
for(i = 1; i <= N; ++ i)
{
P1[i] = (P1[i - 1] * 171) % Mod1;
P2[i] = (P2[i - 1] * 171) % Mod2;
}
for(i = 1; i <= N; ++ i)
{
C1[i] = (C1[i - 1] * 171 + S[i]) % Mod1;
C2[i] = (C2[i - 1] * 171 + S[i]) % Mod2;
}
int Left = 0, Right = N, Mid, Ans = -1;
while(Left <= Right)
{
Mid = (Left + Right) / 2;
if(Check(Mid)) Ans = Mid, Left = Mid + 1;
else Right = Mid - 1;
}
printf("%i\n", Ans);
return 0;
}