Ronzii's Blog

Just your average geek's blog

Rabin Karp Algorithm

#include<cstdio>
#include<iostream>
#include<cstring>
#define d 256
using namespace std;
void search(string pattern, string text, int prime)
{
    int M = pattern.length();
    int N = text.length();
    int h = 1;
    //The value of h would be "pow(d, M-1)%prime"
    for(int i=0; i<M-1; i++)
    {
        h = (h*d)%prime;
    }
    int p = 0,t = 0,i,j;
    // Calculate the hash value of pattern and first window of text
    for(i=0; i<M; i++)
    {
        p = (d*p+pattern[i])%prime;
        t = (d*t+text[i])%prime;
    }
    cout<<p<<endl;
    for(i=0; i<=(N-M); i++)
    {
        if ( p == t )
        {
            // Chaeck the hash values of current window of text and pattern
            // If the hash values match then only check for characters on by one
            for (j = 0; j < M; j++)
            {
                if (text[i+j] != pattern[j])
                    break;
            }
            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            {
                printf("Pattern found at index %d \n", i);
            }
        }
        // Calulate hash value for next window of text: Remove leading digit,
        // add trailing digit
        if(i<(N-M))
        {
            t = ((t - text[i]*h)*d + text[i+M])%prime;
            if(t<0)
            {
                t = t+prime;
            }
        }
    }
}
int main()
{
    string txt = "abacadabrabrarabraabracadcabracadabrabrabracad";
    string pat = "rabrabracad";
    int q = 103;  // A prime number
    search(pat, txt, q);
    return 0;
}

Advertisements

February 26, 2012 Posted by | C++ | , , , , , | Leave a comment