It is just an Implementation of KMP string match Algorithm.
In the first section, I am find the prefix function π for a pattern which
encapsulates knowledge about how the pattern matches
against shifts of itself.
This information can be used in second section to avoid testing useless
shifts for string matching.
On Tue, Jul 27, 2010 at 3:41 AM, bujji <jajalabu...@gmail.com> wrote:
> Hi Anand,
> Can you please explain your code? What is the magic
> number 10 in
> if(k == 10)
> {
> printf("String Matched\n");
> }
>
> in your code?
>
> What does while loop do in your code? Can you please write a comment?
>
> -Thanks in advance,
> Bujji
>
> #include <stdio.h>
> #include <string.h>
> /* KMP algorithm for string Matching */
> main()
> {
> char *p="This is my first post to this group";
> char *T="to this group this is my post";
> int len = strlen(p);
> int len1 = strlen(T);
> printf("len:%d len1:%d\n",len,len1);
> int k = 0,i;
> int
>
> array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
> /* Pre processing which takes O(m)*/
> for(i = 2; i< len; i++)
> {
> while(k > 0 && p[k+1] != p[i])
> {
> k = array[k];
> }
>
> if(p[k+1] == p[i])
> {
> k++;
> array[i] = k;
> }
> }
>
> /* Matching which takes O(n) */
> k = 1;
> for(i = 0; i< len1; i++)
> {
>
> while(k > 0 && p[k+1] != T[i])
> {
> k = array[k];
> }
>
> if(p[k+1] == T[i])
> {
> k++;
> printf("%d %d %c\n",k,i,p[k]);
> if(k == 10)
> {
> printf("String Matched\n");
> }
> }
> }
> }
>
> On Jul 22, 9:22 pm, Anand <anandut2...@gmail.com> wrote:
> > http://codepad.org/grtqfF5f
> >
> > Here is KMP code to solve the problem
> >
> > On Thu, Jul 22, 2010 at 2:01 AM, Mallesh Kavuluri <mallesh...@gmail.com
> >wrote:
> >
> >
> >
> > > Taking for granted that KMP algorithm searches for a given string of
> > > length n in a string of length m in O(n+m) time,
> >
> > > How do we solve this puzzle in linear time?
> >
> > > On Thu, Jul 22, 2010 at 1:29 PM, sharad kumar <aryansmit3...@gmail.com
> >wrote:
> >
> > >> @all:pls make use of KMP algorithm...because knuth morris prat algor
> >
> > >> On Wed, Jul 21, 2010 at 6:16 PM, anugrah <anugrah.agra...@gmail.com
> >wrote:
> >
> > >>> Stack can be used to push the characters of the string A and then
> > >>> popped off while scanning through the string B until there is a
> > >>> difference in the character read from the string B and the one popped
> > >>> off from the stack..
> >
> > >>> On Jul 20, 4:40 pm, agnibha nath <agni.fl...@gmail.com> wrote:
> > >>> > You can try rabin-carp..
> >
> > >>> > On Jul 20, 4:18 pm, mallesh <mallesh...@gmail.com> wrote:
> >
> > >>> > > We are given two strings. A and B.
> >
> > >>> > > First few letters of A match with Last letters of B. We have to
> find
> > >>> > > the longest match in linear time.
> > >>> > > Example:
> > >>> > > char * A ="This is my first post to this group";
> > >>> > > char *B= "to this group this is my post";
> >
> > >>> > > Algorithm should return starting position of substring "to this
> > >>> group"
> > >>> > > in string A.
> >
> > >>> > > How do we do this?
> >
> > >>> > > -Thanks and regards,
> > >>> > > Mallesh
> >
> > >>> --
> > >>> You received this message because you are subscribed to the Google
> Groups
> > >>> "Algorithm Geeks" group.
> > >>> To post to this group, send email to algoge...@googlegroups.com.
> > >>> To unsubscribe from this group, send email to
> > >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > >>> .
> > >>> For more options, visit this group at
> > >>>http://groups.google.com/group/algogeeks?hl=en.
> >
> > >> --
> > >> yezhu malai vaasa venkataramana Govinda Govinda
> >
> > >> --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algoge...@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > >> .
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
