# Cod sursa(job #697112)

Utilizator Data 28 februarie 2012 22:18:02 Substr 90 cpp done Arhiva de probleme 1.16 kb
``````#include <fstream>
#include <cstring>

using namespace std;

const int NLIT = 'z' - 'a' + 1;
const int NCIF = 10;
const int BASE = NLIT + NLIT + NCIF;
const int MOD = 666019;
const int NMAX = 1 << 14;

int N, K, cnt[MOD], poz[MOD];
char S[NMAX];

int normal(char x) {
if ('a' <= x && x <= 'z')
return x - 'a';
if ('A' <= x && x <= 'Z')
return NLIT + x - 'A';
return NLIT + NLIT + x - '0';
}

bool occurence(int l) {
int hash = 0, base = 1;

for (int i = 0; i < l; ++i)
base = (base * BASE) % MOD;

for (int i = 0; i < N; ++i) {
hash = (normal(S[i]) + hash * BASE) % MOD;
if (i >= l) {
hash -= (normal(S[i-l]) * base) % MOD;
if (hash < 0) hash += MOD;
}
if (i + 1 >= l) {
if (poz[hash] == l) {
if (++cnt[hash] >= K)
return true;
} else {
poz[hash] = l;
if ((cnt[hash] = 1) >= K)
return true;
}
}
}
return false;
}

int main(void) {
ifstream fin("substr.in");
ofstream fout("substr.out");

fin >> N >> K >> S;

int step, length;

for (step = 1; (step << 1) < N; step <<= 1);
for (length = 0; step; step >>= 1)
if (occurence(length + step))
length += step;

fout << length << '\n';

fin.close();
fout.close();
}
``````