Rabin-Karp Algorithm in C++

This C++ Program demonstrates the implementation of Rabin-Karp Algorithm.

Here is source code of the C++ Program to demonstrate the implementation of Rabin-Karp Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Rabin-Karp Algorithm

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstring>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
#define d 256
```
```
/*
```
```
 * search a substring in a string 
```
```
 */
```

void search(char *pat, char *txt, int q)

```
{
```
```
    int M = strlen(pat);
```
```
    int N = strlen(txt);
```
```
    int i, j;
```
```
    int p = 0;
```
```
    int t = 0;
```
```
    int 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)
```
```
            {
```

                cout<<"Pattern found at index: "<<i<<endl;

```
            }
```
```
        }
```
```
        if (i < N - M)
```
```
        {
```

            t = (d * (t - txt[i] * h) + txt[i + M]) % q;

```
            if (t < 0)
```
```
              t = (t + q);
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
/* Main */
```
```
int main()
```
```
{
```

    char *txt = "Sanfoundry Linux Training";

```
    char *pat = "nux";
```
```
    int q = 101;
```
```
    search(pat, txt, q);
```
```
    return 0;
```
```
}
```

$ g++ rabinkarp.cpp
$ a.out
 
Pattern found at index: 13
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Print All Permutations using BackTracking

» Next - Sudoku Problem using BackTracking in C++

Related Posts:

Recommended Articles: