Pagini recente » Cod sursa (job #2874201) | Cod sursa (job #1188163) | Cod sursa (job #2768306) | Cod sursa (job #1272171) | Cod sursa (job #1419897)
#include <fstream>
#include <map>
#include <cstring>
using namespace std;
const int kMaxN = 16390;
const int kMaxLg = 16;
int N, K;
char a[kMaxN];
int lg2[kMaxN];
int indx[kMaxLg][kMaxN];
map<pair<int, int>, int> id;
int cnt[kMaxN];
void MakeHash() {
for (int i = 2; i < kMaxN; ++i)
lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= N; ++i)
indx[0][i] = a[i];
for (int i = 1; i < kMaxLg; ++i) {
memset(cnt, 0, sizeof cnt);
int id_crt = 0;
id.clear();
for (int j = 1; j <= N - (1 << i) + 1; ++j) {
auto crt = make_pair(indx[i - 1][j], indx[i - 1][j + (1 << (i - 1))]);
if (!id.count(crt))
id[crt] = ++id_crt;
indx[i][j] = id[crt];
}
}
}
bool Check(int len) {
id.clear();
int lg = lg2[len];
memset(cnt, 0, sizeof cnt);
int id_crt = 0;
for (int i = 1; i <= N - len + 1; ++i) {
auto crt = make_pair(indx[lg][i], indx[lg][i + len - (1 << lg)]);
if (!id.count(crt))
id[crt] = ++id_crt;
if (++cnt[id[crt]] == K)
return true;
}
return false;
}
int Solve() {
int ans = 0;
for (int step = 1 << 14; step; step >>= 1)
if (Check(ans | step))
ans |= step;
return ans;
}
int main() {
ifstream("substr.in") >> N >> K >> (a + 1);
MakeHash();
ofstream("substr.out") << Solve() << "\n";
return 0;
}