plizzzzzzzzzzzzzzzzzz help me in this

[Riyad]

i tried to implement the KMP(Knuth- Morris_Pratt) string matching algorithm but it is not working . plizz some one help me in this . here is the code of mine . i am eagerly waiting for reply .
i found the algorithm in the book of "Cormen "[introduction to algorithms]
in page 926
here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>

char pie[10000];
int q;

void PREFIX_FUNC(char *P){
	
	int m ;
	
	int k ;
	m=strlen(P);
	pie[1]=0;
	k=0;

	for(q=2;q<m;q++){
		do{
			k=pie[k];
			if(P[k+1]==P[q])
				k++;
			pie[q]=k;

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

	//return pie;



}




void KMP_MATCHER(char *T,char *P){
	
	int n , m,i,check=0;
	
	PREFIX_FUNC(P);

	n=strlen(T);
	m=strlen(P);

	q=0;

	for(i=1;i<n;i++){
		do{
		
			q=pie[q];
			if(P[q+1]==T[i])
				q=q+1;
			if(q==m)
				printf("pattern occurs with shift %d",i-m);
			q=pie[q];

			check++;

		}while(q>0 && P[q+1]!=T[i]);

			//q=pie[q];
	
	}

	//printf("i am out   %d\n",check);


}



int main(){

	char T[1000],P[500];
	
	gets(T);
	gets(P);

	KMP_MATCHER(T,P);

	
	
	return 0;
} 

Eagerly waiting for reply
Bye
Riyad

[filipek]

[cpp]
for(i=1;i<n;i++){
do{

q=pie[q];
if(P[q+1]==T)
q=q+1;
if(q==m)
printf("pattern occurs with shift %d",i-m);
q=pie[q];

check++;

}while(q>0 && P[q+1]!=T);
[/cpp]

I'm not sure i did understood your code (i use Pascal), but, as i see
1. If, at the beginning of a loop, q=m-1, so you nearly found a match, you execute q=pie[q] - you shouldn't, first you should make sure, that P[q+1]!=T.
2. Even if you find a match here :
[cpp]
if(P[q+1]==T)
q=q+1;
[/cpp]
You will forget about this discovery after executing, again, q=pie[q], before coming to the end of a loop.

Best regards,

Furippo