Robin-Karp String Matching

#include<stdio.h>
#include<string.h>
#define d 256

void search(char *pat,char *txt,int q)
{
    int m=strlen(pat);
    int n=strlen(txt);
    int i ,j;
    int p=0,t=0,h=1;
    for(i=0;i<m-1;i++)
        h=(h*d)%q;
    for(i=0;i<m;i++)
    {
        p=(d*p+pat[i])%q;
        t=(d*t+txt[i])%q;
    }
    for(i=0;i<=n-m;i++)
    {
        if(p==t)
        {
            for(j=0;j<m;j++)
            {
                if(txt[i+j]!=pat[j])
                    break;
            }
            if(j==m)
            {
                printf("\nPattern %s found in text: %s at index %d\n",pat,txt,i);
            }
        }
        if(i<n-m)
        {
            t=(d*(t-txt[i]*h)+txt[i+m])%q;
            if(t<0)
                t=(t+q);
        }
    }
}

void main()
{
    char *txt="Naruto is the best !! Naruto Daisuki";
    char *pat="Naruto";
    int q=101;
    search(pat,txt,q);
}

/*Output

Pattern Naruto found in text: Naruto is the best !! Naruto Daisuki at index 0

Pattern Naruto found in text: Naruto is the best !! Naruto Daisuki at index 22

*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s