Cod sursa(job #426)

Utilizator alextheroTandrau Alexandru alexthero Data 11 decembrie 2006 11:20:46
Problema Substr Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 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;
}