Ignore the last post.
match(char * A, char *B) {
char * tempA = *A;
while(1) {
char * tempB=*B;
while(*B && *B == *A) {
*B++;
*A++;
}
if(!*B)
return *tempB;
else {
while(*B && *B != *A){
*B++ ;
}
if(*B) {
*A = *tempA;
continue;
}
else
return NULL;
} //while(1)
}//match()
On Wed, Jul 28, 2010 at 1:32 PM, Shiv ... <shivsinha2...@gmail.com> wrote:
> Excuse the indentations, how about the following solution? O(strlen(B)).
>
> match(char * A, char *B) {
> char * tempA = *A;
> while(1) {
> char * tempB=*B;
> while(*B && *B == *A) {
> *B++;*A++;
> }
>
> if(!*B)
> return *tempB;
> else {
> while(*B && *B++ != *A) ;
> if(*B)
> continue;
> else
> return NULL;
> } //while(1)
> }//match()
>
> -Shiv
>
>
> On Wed, Jul 28, 2010 at 3:41 AM, Anand <anandut2...@gmail.com> wrote:
>
>> 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<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.
