It is string searching algorithm in which basically two strings given -a text and a pattern, and it determine whether the pattern appears in the text. Knuth, Morris and Pratt (KMP) discovered this algorithm by close analysis of the naive algorithm and then proposed a linear time algorithm for the string matching problem. This algorithm is used in Text editors, search engines, digital library systems and even some intrusion detection systems also. It is also used in bio-informatics along with some other algorithms such as longest common subsequence (LCS). Here we have implemented KMP string matching algorithm in C++. Following algorithm demonstrates linear time running time for string matching.

#include <iostream>
#include <cstring>
using namespace std;
void prefix(string pat, int Pi[])
{
	int m = pat.length(), k;
	Pi[0] = -1;
	for (int i = 1; i < m; i++)
	{
		k = Pi[i - 1];
		while (k >= 0)
		{
			if (pat[k] == pat[i - 1])
				break;
			else
				k = Pi[k];
		}
		Pi[i] = k + 1;

    }
}
//check whether target string contains pattern 
bool KMP(string pat, string target)
{
    int m = pat.length();
    int n = target.length();
    int Pi[m];     
    prefix(pat, Pi);     
    int i = 0;
    int k = 0;        
    while (i < n)
    {
        if (k == -1)
		{
			i++;
			k = 0;
		}
		else if (target[i] == pat[k])
		{
			i++;
			k++;
			if (k == m)
			return 1;
		}
		else
			k = Pi[k];
	}
	return 0;
}
int main()
{
    string tar = "Welcome to sourcecodemania.com";
	string pat = "come";
	if (KMP(pat, tar))
		cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
	else
		cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
	
	pat = "Weldone";
	if (KMP(pat, tar))
		cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
	else
		cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;

    return 0;
}
Tagged with: C/C++ languageSource Code
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.