PHP-Fusion Powered Website - Articles: C++ Program to Implement KMP Pattern Searching Algorithm

Users Online

· Guests Online: 113

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Implement KMP Pattern Searching Algorithm

C++ Program to Implement KMP Pattern Searching Algorithm

This C++ Program demonstrates the implementation of Knuth–Morris–Pratt Algorithm popularly known as KMP.

Here is source code of the C++ Program to implement Knuth–Morris–Pratt Algorithm (KMP). The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * 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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

C++ Program to Implement KMP Pattern Searching Algorithm

C++ Program to Implement KMP Pattern Searching Algorithm

Comments

Post Comment

Ratings