#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
#define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
TcT> bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT> bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define TC 0
if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */
template <int Mod, int Base>
struct Hashing {
int n;
vector <int> Num;
vector <int> prefHash, suffHash;
vector <int> Pow;
public:
Hashing(){}
Hashing(const string &s) {
n = sz(s);
Num.assign(n + 1, 0);
prefHash.assign(n + 1, 0), suffHash.assign(n + 2, 0);
Pow.assign(n + 1, 0);
for (int i = 0; i < n; ++i)
Num[i + 1] = s[i] - 'a' + 1;
}
Hashing(const vector <int> &num) { // idx from 1
n = sz(num) - 1;
Num.assign(n + 1, 0);
prefHash.assign(n + 1, 0), suffHash.assign(n + 2, 0);
Pow.assign(n + 1, 0);
for (int i = 1; i <= n; ++i)
Num[i] = num[i];
}
void init() { return void(initialize()); }
int getPrefHash(int l, int r) { return getPref(l, r); } // idx from 1
int getSuffHash(int l, int r) { return getSuff(l, r); } // idx from 1
bool isPalin() { return palin(1, n); }
bool isPalin(int l, int r) { return palin(l, r); }
private:
void initialize() {
Pow[0] = 1;
for (int i = 1; i <= n; ++i)
Pow[i] = (Pow[i - 1] * Base) % Mod;
for (int i = 1; i <= n; ++i) {
prefHash[i] = (prefHash[i - 1] * Base + Num[i]) % Mod;
suffHash[n - i + 1] = (suffHash[n - i + 2] * Base + Num[n - i + 1]) % Mod;
}
}
int getPref(int left, int right) { // idx from 1
return (prefHash[right] - prefHash[left - 1] * Pow[right - left + 1] + Mod * Mod) % Mod;
}
int getSuff(int left, int right) {
return (suffHash[left] - suffHash[right + 1] * Pow[right - left + 1] + Mod * Mod) % Mod;
}
bool palin(int l, int r) {
return getPref(l, r) == getSuff(l, r);
}
};
using Hash = Hashing <MOD, 31>;
bool check(int len, int n, int k, Hash &H) {
map <int, int> cnt;
for (int i = 1; i <= n - len + 1; ++i)
if (++cnt[H.getPrefHash(i, i + len - 1)] >= k)
return true;
return false;
}
void solve() {
int n, k; cin >> n >> k;
string s; cin >> s;
Hash H(s); H.init();
int ans = 0;
int lo = 1, hi = n;
while (lo <= hi) {
/// dap an la 3
int mid = (lo + hi) >> 1;
if (check(mid, n, k, H))
ans = mid, lo = mid + 1;
else
hi = mid - 1;
}
cout << ans << '\n';
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojaWZkZWYgT1BfREVCVUcKICAgICNpbmNsdWRlIDxhbGdvL2RlYnVnLmg+CiNlbHNlCiAgICAjZGVmaW5lIGRlYnVnKC4uLikgMjYKI2VuZGlmCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBpbnQgCWxvbmcgbG9uZwojZGVmaW5lIHN6KHYpICAgKGludCkodikuc2l6ZSgpCiNkZWZpbmUgYWxsKHYpICAodikuYmVnaW4oKSwgKHYpLmVuZCgpCiNkZWZpbmUgVGNUICAgICB0ZW1wbGF0ZSA8Y2xhc3MgVAoKY29uc3QgICBpbnQgICAgIE1PRCA9IChpbnQpMWU5ICsgNywgSU5GID0gKGludCk0ZTE4ICsgMTg7CgpUY1Q+ICAgICAgICAgICAgYm9vbCBtaW5pbWl6ZShUICZsaHMsIGNvbnN0IFQgJnJocykgeyByZXR1cm4gcmhzIDwgbGhzID8gbGhzID0gcmhzLCAxIDogMDsgfQpUY1Q+ICAgICAgICAgICAgYm9vbCBtYXhpbWl6ZShUICZsaHMsIGNvbnN0IFQgJnJocykgeyByZXR1cm4gcmhzID4gbGhzID8gbGhzID0gcmhzLCAxIDogMDsgfQoKdm9pZCBzb2x2ZSgpOwoKaW50MzJfdCBtYWluKCkgewogICAgY2luLnRpZShudWxscHRyKSwgY291dC50aWUobnVsbHB0cikgLT4gc3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGludCB0ZXN0Y2FzZXMgPSAxOwoKI2RlZmluZSBUQyAwCiAgICBpZiAoVEMpIHsgY2luID4+IHRlc3RjYXNlczsgfSBmb3IgKDsgdGVzdGNhc2VzLS07KSB7IHNvbHZlKCk7IH0KfQoKLyogW1BoYW0gSHVuZyBBbmggLSAxMUkgLSBUcmFuIEh1bmcgRGFvIEhpZ2ggU2Nob29sIGZvciBHaWZ0ZWQgU3R1ZGVudF0gKi8KCnRlbXBsYXRlIDxpbnQgTW9kLCBpbnQgQmFzZT4Kc3RydWN0IEhhc2hpbmcgewogICAgaW50IG47CiAgICB2ZWN0b3IgPGludD4gTnVtOwogICAgdmVjdG9yIDxpbnQ+IHByZWZIYXNoLCBzdWZmSGFzaDsKICAgIHZlY3RvciA8aW50PiBQb3c7CgpwdWJsaWM6CiAgICBIYXNoaW5nKCl7fQogICAgSGFzaGluZyhjb25zdCBzdHJpbmcgJnMpIHsKICAgICAgICBuID0gc3oocyk7CiAgICAgICAgTnVtLmFzc2lnbihuICsgMSwgMCk7CiAgICAgICAgcHJlZkhhc2guYXNzaWduKG4gKyAxLCAwKSwgc3VmZkhhc2guYXNzaWduKG4gKyAyLCAwKTsKICAgICAgICBQb3cuYXNzaWduKG4gKyAxLCAwKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpCiAgICAgICAgICAgIE51bVtpICsgMV0gPSBzW2ldIC0gJ2EnICsgMTsKICAgIH0KICAgIEhhc2hpbmcoY29uc3QgdmVjdG9yIDxpbnQ+ICZudW0pIHsgLy8gaWR4IGZyb20gMQogICAgICAgIG4gPSBzeihudW0pIC0gMTsKICAgICAgICBOdW0uYXNzaWduKG4gKyAxLCAwKTsKICAgICAgICBwcmVmSGFzaC5hc3NpZ24obiArIDEsIDApLCBzdWZmSGFzaC5hc3NpZ24obiArIDIsIDApOwogICAgICAgIFBvdy5hc3NpZ24obiArIDEsIDApOwoKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpCiAgICAgICAgICAgIE51bVtpXSA9IG51bVtpXTsKICAgIH0KCiAgICB2b2lkIGluaXQoKSAgICAgICAgICAgICAgICAgICB7IHJldHVybiB2b2lkKGluaXRpYWxpemUoKSk7IH0KCiAgICBpbnQgZ2V0UHJlZkhhc2goaW50IGwsIGludCByKSB7IHJldHVybiBnZXRQcmVmKGwsIHIpOyAgICAgIH0gLy8gaWR4IGZyb20gMQogICAgaW50IGdldFN1ZmZIYXNoKGludCBsLCBpbnQgcikgeyByZXR1cm4gZ2V0U3VmZihsLCByKTsgICAgICB9IC8vIGlkeCBmcm9tIDEKCiAgICBib29sIGlzUGFsaW4oKSAgICAgICAgICAgICAgICB7IHJldHVybiBwYWxpbigxLCBuKTsgICAgICAgIH0KICAgIGJvb2wgaXNQYWxpbihpbnQgbCwgaW50IHIpICAgIHsgcmV0dXJuIHBhbGluKGwsIHIpOyAgICAgICAgfQoKcHJpdmF0ZToKICAgIHZvaWQgaW5pdGlhbGl6ZSgpIHsKICAgICAgICBQb3dbMF0gPSAxOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkKICAgICAgICAgICAgUG93W2ldID0gKFBvd1tpIC0gMV0gKiBCYXNlKSAlIE1vZDsKCiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgICAgIHByZWZIYXNoW2ldID0gKHByZWZIYXNoW2kgLSAxXSAqIEJhc2UgKyBOdW1baV0pICUgTW9kOwogICAgICAgICAgICBzdWZmSGFzaFtuIC0gaSArIDFdID0gKHN1ZmZIYXNoW24gLSBpICsgMl0gKiBCYXNlICsgTnVtW24gLSBpICsgMV0pICUgTW9kOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgZ2V0UHJlZihpbnQgbGVmdCwgaW50IHJpZ2h0KSB7IC8vIGlkeCBmcm9tIDEKICAgICAgICByZXR1cm4gKHByZWZIYXNoW3JpZ2h0XSAtIHByZWZIYXNoW2xlZnQgLSAxXSAqIFBvd1tyaWdodCAtIGxlZnQgKyAxXSArIE1vZCAqIE1vZCkgJSBNb2Q7CiAgICB9CgogICAgaW50IGdldFN1ZmYoaW50IGxlZnQsIGludCByaWdodCkgewogICAgICAgIHJldHVybiAoc3VmZkhhc2hbbGVmdF0gLSBzdWZmSGFzaFtyaWdodCArIDFdICogUG93W3JpZ2h0IC0gbGVmdCArIDFdICsgTW9kICogTW9kKSAlIE1vZDsKICAgIH0KCiAgICBib29sIHBhbGluKGludCBsLCBpbnQgcikgewogICAgICAgIHJldHVybiBnZXRQcmVmKGwsIHIpID09IGdldFN1ZmYobCwgcik7CiAgICB9Cn07Cgp1c2luZyBIYXNoID0gSGFzaGluZyA8TU9ELCAzMT47Cgpib29sIGNoZWNrKGludCBsZW4sIGludCBuLCBpbnQgaywgSGFzaCAmSCkgewogICAgbWFwIDxpbnQsIGludD4gY250OwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbiAtIGxlbiArIDE7ICsraSkKICAgICAgICBpZiAoKytjbnRbSC5nZXRQcmVmSGFzaChpLCBpICsgbGVuIC0gMSldID49IGspCiAgICAgICAgICAgIHJldHVybiB0cnVlOwoKICAgIHJldHVybiBmYWxzZTsKfQoKdm9pZCBzb2x2ZSgpIHsKICAgIGludCBuLCBrOyBjaW4gPj4gbiA+PiBrOwogICAgc3RyaW5nIHM7IGNpbiA+PiBzOwoKICAgIEhhc2ggSChzKTsgSC5pbml0KCk7CgogICAgaW50IGFucyA9IDA7CiAgICBpbnQgbG8gPSAxLCBoaSA9IG47CiAgICB3aGlsZSAobG8gPD0gaGkpIHsKICAgICAgICAvLy8gZGFwIGFuIGxhIDMKICAgICAgICBpbnQgbWlkID0gKGxvICsgaGkpID4+IDE7CgogICAgICAgIGlmIChjaGVjayhtaWQsIG4sIGssIEgpKQogICAgICAgICAgICBhbnMgPSBtaWQsIGxvID0gbWlkICsgMTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGhpID0gbWlkIC0gMTsKICAgIH0KCiAgICBjb3V0IDw8IGFucyA8PCAnXG4nOwp9Cg==