NAJPF - Pattern Find and KMP String matching Algorithm Example Problem SPOJ - UCS - Unleash-Coding-Skills

## NAJPF - Pattern Find

This is an example to practice for  Knuth-Moris-Pratt(KMP) Pattern Matching(Substring Search)

The link for this problem is:

http://www.spoj.com/problems/NAJPF/

In this, we directly applied KMP pattern Matching algorithm.The KMP pattern matching takes O(n+m) time complexity where n is a length of String and m is a length of the pattern.

The following is CPP solution for NAJPF - Pattern Find problem spoj.

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

long int kmphelper[100002];

vector<long int>v;

string str,pat;

long int len1,len2;

{

v.clear();

long i=0,j=0;

int flag=0;
while(i<len1)
{
if(str[i]==pat[j])
{

i++;
j++;
if(j==len2)
{
flag=1;
j=0;
long int r =i-len2+1;
i=i-len2+1;
v.push_back(r);
}
}
else
{
if(j!=0)
{
j=kmphelper[j-1];
}
else
{
i++;
}
}
}
if(flag==1)
{
cout<<v.size()<<endl;
for(long int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
}
if(flag==0)
{
}
cout<<endl;
}
void makekmphelper(){
long int i,j,k;
j=0;
i=1;
kmphelper[0]=0;
while(i<len2)
{
if(pat[i]==pat[j])
{
kmphelper[i]=j+1;
i++;
j++;
}
else
{
if(j!=0)
{
j=kmphelper[j-1];
}
else
{
kmphelper[i]=0;
i++;
}
}
}
}
int main()
{
long int t,i,j,k,n,m;
cin>>t;
for(long int ii=0;ii<t;ii++)
{
cin>>str;
cin>>pat;
len1 = str.length();
len2 = pat.length();
for(i=0;i<len2;i++)
kmphelper[i]=0;
makekmphelper();
cout<<endl;
}

return 0;
}

Happy Coding....................