Cod sursa(job #425)

Utilizator alextheroTandrau Alexandru alexthero Data 11 decembrie 2006 11:17:32
Problema Substr Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>

#define nmax 20005
#define hash_mod 498987
#define baza 13

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

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 cauta(int first,int last) {
    int r=0;
    while(first<=last) {
                       int middle=(first+last)/2;
                       if(ok(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;
}