Friday, October 2, 2015

Implmentation of Rabin-Karp Algorithm in c

#include <stdio.h>
#include<stdlib.h>
int hash (char * a,int s,int t)
{ int h=0;
    for(;s<=t;s++)
        h+=a[s];
       return h;
}
int match(char * a,int a1,int a2,char * b, int b1,int b2)
{  
    for(;a1<=a2,b1<=b2;a1++,b1++)
       { if(a[a1]!=b[b1])
           return 0;
       }
       return 1;
}   
   

void rk(char*a,char *b,int as,int bs)

   int ph=hash(b,0,bs-1),i;
   for(i=0;i<(as-bs+1);i++)
    { if(hash(a,i,i+bs-1)==ph)
        if(match(a,i,i+bs-1,b,0,bs-1))
      { printf("  match for < %s > found at position : %d ",b,i+1);}
    }
        
    
}
void main()
{  
 char t[]="abcdefghijklmnopqrstuvwxyz";
 char p[]="klmnop";
    int st=sizeof(t)-1;
    int  sp=sizeof(p)-1;
    rk(t,p,st,sp);
    
    
}