Pagini recente » Cod sursa (job #2009329) | Monitorul de evaluare | Cod sursa (job #2058138) | Cod sursa (job #2954767) | Cod sursa (job #1007482)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <map>
#define Base 73
#define Mod1 666013
#define Mod2 515423
#define Nmax 16500
using namespace std;
int n,K;
char s[Nmax];
int Pow1[Nmax],a[Mod1];
map < int,int >M;
inline bool Verif(const int k)
{
int i,Hash1 = 0,Hash2 = 0,P1 = 1,P2 = 1,Hash;
M.clear();
for(i = 1;i <= k; ++i)
{
Hash1 = (Hash1*Base+s[i])%Mod1;
Hash2 = (Hash2*Base+s[i])%Mod2;
if(i < k)
P1 = (P1*Base)%Mod1,
P2 = (P2*Base)%Mod2;
}
Hash = Hash1 + Hash2;
++M[Hash];
for(i=k+1;i<=n;++i)
{
Hash1 = ((Hash1 - (s[i - k] * P1) % Mod1 + Mod1) * Base + s[i]) % Mod1;
Hash2 = ((Hash2 - (s[i - k] * P2) % Mod2 + Mod2) * Base + s[i]) % Mod2;
Hash = Hash1 + Hash2;
if(++M[Hash] >= K)
return true;
}
return false;
}
int main()
{
ifstream f("substr.in");
f>>n>>K>>(s+1);
f.close();
int Left = 0,Right = n,Middle, sol = 0;
if(K!=1)
while(Left<=Right)
{
Middle = (Left+Right)>>1;
if(Verif(Middle))
{
sol = Middle;
Left = Middle + 1;
}
else
Right = Middle-1;
}
else
sol = n;
ofstream g("substr.out");
g<<sol<<"\n";
g.close();
return 0;
}