Knuth Morris Pratt Algorithm

[#include_rose]

Hey guys, I have implemented the Knuth Morris Pratt algorithm and wanted to share the C code with all of you. If you feel it can be optimized please let me know. Feel free to play with it or use it for your school work :icon_biggrin:

*************************KMP******************************

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

static kmp(char *ptr_i,char *ptr_m,int word_length,int sentence_length);
static kmp_table(char *ptr_i,char *ptr_m,int word_length,int sentence_length);
char T[50];

int main()
{
char word[10],sentence[40];
char *ptr_i,*ptr_m;
int word_length,sentence_length;
ptr_i=word;
ptr_m=sentence;
printf("Enter the word");
scanf("%s",&word);
word_length=strlen(word);
getchar();
printf("Enter the sentence\n");
fgets(sentence,40,stdin);
sentence_length=strlen(sentence);
kmp_table(ptr_i,ptr_m,word_length,sentence_length);
kmp(ptr_i,ptr_m,word_length,sentence_length);

}

kmp(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
  int pos,m=0,i=0;
  for(;m<sentence_length; )
    {
      if(*(ptr_i+i) == *(ptr_m+m+i))
        {
          i=i+1;
        if(i==word_length)
         {
           pos=m+1;
           printf("The word was found at position %d\n",pos );
         }

        }
       else
        {

         m=m+i-T[i];
         if(i>0)
         i=T[i];

        }
    }

      return sentence_length;
}


kmp_table(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
 int i,j;
  i=2;
  j=0;
  T[0]=-1;
  T[1]=0;
  for(;i<word_length; )
  {
        if(*(ptr_i+i-1) == *(ptr_i+j))
           {
            T[i]=j+1;
            i=i+1;
            j=j+1;
           }

        else if(j>0)
            {
             j=T[j];
            }

        else
            {
             T[i]=0;
             i=i+1;
            }
 }


}

***********************************************************
Author: Rose

[Aia]

>or use it for your school work
Yeah, tun it in for a grade. Don't be surprise of the F afterwards.

char word[10]
scanf("%s",&word);

Word is a string. So, you don't need the & in the scanf function.

[#include_rose]

Thanks for pointing that out. You didn't have to be so mean. We all make mistakes.

[Aia]

Thanks for pointing that out. You didn't have to be so mean. We all make mistakes.

Believe me, I wasn't being mean. I was warning any one of getting
a F by turning your code in. Your code doesn't work. Have you tried it?

[#include_rose]

Hmm, let me see, maybe I posted the older version. Let me recheck!

[#include_rose]

Woops, this code does work. Try giving this:
word : sue
sentence : i am sue.
It gives you the correct position.

[#include_rose]

And ofcourse if you exceeded the length of the word/sentence, it won't work!! You would have to allocate memory dynamically to make that work!

[Ancient Dragon]

scanf() with "%s" (see line 16 of your program), like its cousin gets(), should never ever in this lifetime be used for any purpose Its an evil function that will cripple your program and possibly crash the os. Instead, use fgets() which limits imput to the size of the input buffer.

I don't know if your version works or not (didn't test it) but this probably does.

[#include_rose]

scanf() with "%s" (see line 16 of your program), like its cousin gets(), should never ever in this lifetime be used for any purpose Its an evil function that will cripple your program and possibly crash the os. Instead, use fgets() which limits imput to the size of the input buffer.

I don't know if your version works or not (didn't test it) but this probably does.

I thought this only happens for the gets function. Didn't know anything about scanf, is working fine on my system, thanks for letting me know!

[TkTkorrovi]

Ancient Dragon is right what concerns scanf. I thus say that in the capacity of the right shouter, like in a meeting someone shouting "that's right", may significantly increase the credibility of the statement made by some other person. Additionally, scanf is a proper function only on condition that no one would enter more text than the variables into which we read, can take. :) :)

[Aia]

I thought this only happens for the gets function.

The gets function, in loose terms, reads any character entered into the usually stdin buffer. It doesn't care how much space is set apart for the string. If the buffer content is bigger that the space allocated for it, it will overrun and keep writing into memory not set for it.

Didn't know anything about scanf,

Scanf at the other hand, is the opposite. It will only read some specific amount of characters. Leaving behind anything else that the function doesn't accept. What happens to input left in the standard buffer? It will be there available to screw you up at the next request to read from it.

is working fine on my system, thanks for letting me know!

It's not fine. Enter word: sue followed by a space and enter. You'll see the result of what I have been explaining.

BTW: I like your nick name #include_rose.

[Ancient Dragon]

It's not fine. Enter word: sue followed by a space and enter. You'll see the result of what I have been explaining.

Another experiment -- enter a sequence of characters with no spaces that is longer than the size of the imput buffer and see what happens ;)

[anjaly grace]

//this is a c++ code, not dynamic memory allocation. 
//for nitc students (who might use it in 2010)



#include<iostream.h>
#include<conio.h>
#include<string.h>
void kmp();
void time(char p[]);
void kmp();
char p[100],s[100];
int t[100];
int m;
int main()
{
clrscr();
cout<<"enter string"<<endl;
cin>>s;
cout<<"enter pattern"<<endl;
cin>>p;
m=strlen(p);
kmp();
getch();
return (0);
}
void time(char p[10])
{
int k=0;
t[0]=0;
m=strlen(p);
int i;
for(int q=1;q<m;q++)
{

while((k>(0))&&(p[k]!=p[q]))
  {

  k=t[k-1];
   }

if(p[k]==p[q])
 { k=k+1;  }

t[q]=k;
}
//for(i=0;i<m;i++)
//cout<<t[i]<<", ";
//cout<<"\n";
}

	int flag=1;
void kmp()
{
 int m,n,q,i;

 n=strlen(s);
 m=strlen(p);

 time(p);
 q=0;

 for(i=0;i<n;i++)
   {
    while(q>(0)&&p[q]!=s[i])
       q=t[q-1];

    if(p[q]==s[i])
      q=q+1;

    if(q==m)
     {
      cout<<"Pattern match occurs at"<<(i-m+1)<<endl;
      q=t[q-1];
      flag=0;
     }
   }
   if(flag==1)
   cout<<"pattern doesnot match ";
}

[MosaicFuneral]

Why did you revive a dead thread? You did not use code tags(site rule) leaving it unformatted, and we have section for posting code snippets.

Why is there .h's after your C++ headers? Why is there no breaks/newlines between your code? Why are you using non-standard functions, where not needed?

[jephthah]

for nitc students (who might use it in 2010)

more like, for nitc students who want an example of what NOT to do.

i keep getting told that NIT universities in india are premiere. you sure cant tell by the ones who come here posting on this site.

:|

.