PHP-Fusion Powered Website

```
/*
```

 * C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)

```
 */
```
```
#include <iostream>
```
```
#include <cstring>
```
```
using namespace std;
```
```
void preKMP(string pattern, int f[])
```
```
{
```
```
    int m = pattern.length(), k;
```
```
    f[0] = -1;
```
```
    for (int i = 1; i < m; i++)
```
```
    {
```
```
        k = f[i - 1];
```
```
        while (k >= 0)
```
```
        {
```

            if (pattern[k] == pattern[i - 1])

```
                break;
```
```
            else
```
```
                k = f[k];
```
```
        }
```
```
        f[i] = k + 1;
```
```
    }
```
```
}
```
```
 
```

//check whether target string contains pattern

```
bool KMP(string pattern, string target)
```
```
{
```
```
    int m = pattern.length();
```
```
    int n = target.length();
```
```
    int f[m];     
```
```
    preKMP(pattern, f);     
```
```
    int i = 0;
```
```
    int k = 0;        
```
```
    while (i < n)
```
```
    {
```
```
        if (k == -1)
```
```
        {
```
```
            i++;
```
```
            k = 0;
```
```
        }
```

        else if (target[i] == pattern[k])

```
        {
```
```
            i++;
```
```
            k++;
```
```
            if (k == m)
```
```
                return 1;
```
```
        }
```
```
        else
```
```
            k = f[k];
```
```
    }
```
```
    return 0;
```
```
}
```
```
 
```
```
int main()
```
```
{
```

    string tar = "san and linux training";

```
    string pat = "lin";
```
```
    if (KMP(pat, tar))
```

        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;

```
    else
```

        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;

```
    pat = "sanfoundry";
```
```
    if (KMP(pat, tar))
```

        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;

```
    else
```

        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;

```
    return 0;
```
```
}
```

$ g++ kmp.cpp
$ a.out
 
'lin' found in string 'san and linux training'
'sanfoundry' not found in string 'san and linux training'
 
------------------
(program exited with code: 1)
Press return to continue

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