KMP implementation

[Fouj]

please help me in removing the error :( im not getting it..ur help will be appreciated.

#include<iostream>

using namespace std;

int *prefunc(string p){
	int m=p.size(), k=0;
	int *pi=new int[m];
	pi[1]=0;
	for(int q=2;q<m;q++){
		while(k>0 && p[k+1]!=p[q]){
			k=pi[k];
		}
		if(p[k+1]==p[q])
			k=k+1;
		pi[q]=k;
	}
	return pi;
}


int KMP_Matcher(string s, string p){
	int *pi;
	int n=s.size();
	int m=p.size();
	pi=prefunc(p);
	int q=0;
	for(int i=1;i<=n;i++){
		while(q>0 && p[q+1]!=s[i]){
			q=pi[q];
		}
		if(p[q+1] == s[i]){
			q++;
		}
		if(q==m){
			return(i-m);
		}
		q=pi[q];
	}
	return 0;
}

void main(){
	int x;
	string s="bacbabababacaab";
	string p="ababaca";
	x=KMP_Matcher(s,p);
	if(x==0)
		cout<<"\nNo match found\n";
	else
		cout<<"\nPattern occurs with shift "<<x;
}

[tipaye]

What specific problem do you want help with? What error(s) are you getting and when?

[Fouj]

there is a garbage value in q of KMP_Matcher

[Fouj]

if(p[q+1]==s[i])
i think at this line is some problem

[tipaye]

Hi,

I still haven't worked out the logic (no time or energy :0), so I don't know what you're trying to accomplish.

Can you explain what you're trying to do, that speeds things up for everyone.

In the mean time, look at lines 6 and 10-12:

int m=p.size(), k=0;

while(k>0 && p[k+1]!=p[q]){
	k=pi[k];
}

That while loop will never run, because you initialise k to 0, you never change it, and then ask the loop to only run when k > 0.

You've done the same thing in lines 26 - 30.

Also, check for zero-based indexing and memory leaks...