# Cod sursa(job #426)

Utilizator Data 11 decembrie 2006 11:20:46 Substr 90 cpp done Arhiva de probleme 2.49 kb
``````#include <stdio.h>

#define nmax 20005
#define hash_mod 498987
#define baza 7
#define hash_mod1 498983
#define baza1 17

char a[nmax];
int n,k;
int hash[hash_mod],hash1[hash_mod1];

int ok(int q) {
for(int i=0;i<hash_mod;i++) hash[i]=0;
int hesh=0,powmare=1;
for(int i=1;i<q;i++) {
hesh=hesh*baza+a[i];
hesh%=hash_mod;
if(hesh<0) hesh+=hash_mod;
powmare=powmare*(baza);
powmare%=hash_mod;
if(powmare<0) powmare+=hash_mod;
}
for(int i=q;i<=n;i++) {
hesh=hesh*baza+a[i];
hesh%=hash_mod;
if(hesh<0) hesh+=hash_mod;
hash[hesh]++;
if(hash[hesh]>=k) return 1;
hesh=hesh-a[i-q+1]*powmare;
hesh%=hash_mod;
if(hesh<0) hesh+=hash_mod;
}
return 0;
}

int ok1(int q) {
for(int i=0;i<hash_mod1;i++) hash1[i]=0;
int hesh1=0,powmare1=1;
for(int i=1;i<q;i++) {
hesh1=hesh1*baza1+a[i];
hesh1%=hash_mod1;
if(hesh1<0) hesh1+=hash_mod1;
powmare1=powmare1*(baza1);
powmare1%=hash_mod1;
if(powmare1<0) powmare1+=hash_mod1;
}
for(int i=q;i<=n;i++) {
hesh1=hesh1*baza1+a[i];
hesh1%=hash_mod1;
if(hesh1<0) hesh1+=hash_mod1;
hash1[hesh1]++;
if(hash1[hesh1]>=k) return 1;
hesh1=hesh1-a[i-q+1]*powmare1;
hesh1%=hash_mod1;
if(hesh1<0) hesh1+=hash_mod1;
}
return 0;
}

int cauta(int first,int last) {
int r=0;
while(first<=last) {
int middle=(first+last)/2;
if((ok(middle)) && (ok1(middle))) {
r=middle;
first=middle+1;
}
else last=middle-1;
}
return r;
}

int main() {
freopen("substr.in","r",stdin);
freopen("substr.out","w",stdout);

scanf("%d %d\n",&n,&k);
for(int i=1;i<=n;i++) scanf("%c",&a[i]);

int x=cauta(1,n);
printf("%d\n",x);
return 0;
}
``````