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>
> >>> .
> >>> 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>
> >> .
> >> 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>
> > .
> > 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
