#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    68
    Rep Power
    0

    Boyre moore string comparison


    hello friends ,
    I am trying to implement boyre moore algorithm for string comparison..

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<malloc.h>
    //boyre moore string algorithm
    /*  given: ABXBABC
    	find:  ABC
    */
    
    void boyre(char *str1,char *str2,int maxpos1,int maxpos2)
    	{
    		char ch[10];
    		str1=malloc(10*sizeof(char));
    	 	str2=malloc(10*sizeof(char));
    	 //	ch=malloc(10*sizeof(char));
    	 	
    	 	while(maxpos2>=0)
    	 		if(str1[maxpos2]==str2[maxpos2])
    			{
    				//compare prev element
    				ch[maxpos2]=str1[maxpos2];
    				maxpos2--;
    				boyre(str1,str2,maxpos1,maxpos2);
    			}
    			else
    			{
    				maxpos2=maxpos2+maxpos2+1;
    				boyre(str1,str2,maxpos1,maxpos2);
    			}
    		if(maxpos2==maxpos1)
    			printf("\n no match found");
    
    	        puts(ch);
    		}
    
    int main()
    	 {
    	 	char *str1;
    	 	char *str2;
    	 	int len1,len2;
    	 	int maxpos1,maxpos2;
    	 //	int i=0;
    	 	
    	 	str1=malloc(10*sizeof(char));
    	 	str2=malloc(10*sizeof(char));
    	 	
    	 	printf("Enter string you want to compare with :\n");
    	 	gets(str1);
    	 	printf("Enter comparison string :\n");
    	 	gets(str2);
    	 	
    	 	len1=strlen(str1);
    	 	len2=strlen(str2);
    		
    		printf("%d",len1);
    		printf("%d",len2);
    		
    		maxpos1=len1-1;
    		maxpos2=len2-1; 
    		
    		boyre(str1,str2,maxpos1,maxpos2);
    	
    
    
    	 getch();
    	 return 0;
    	 }
    What i have tried so far:
    string:ABCXABXC
    comparewith:ABC

    started from right of comparewith string ie C if match found then i decrement my position and check for B and so on .. if not I jump n positions ahead ..
    where n=string length of comparewith string.....

    I have problems in code....

    I have understood algorithm only this far... any additons to check?
    Last edited by swapy; February 5th, 2013 at 02:09 AM.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,902
    Rep Power
    481
    Code:
    void boyre(char *str1,char *str2,int maxpos1,int maxpos2)
    	{
    		char ch[10];
    		str1=malloc(10*sizeof(char));
    	 	str2=malloc(10*sizeof(char));
    Let's pretend that you know to never use gets because of the inherent buffer overrun problem. You've passed information to your boyre function then immediately lose track of it by allocating new space. Frankly, I expected quite a different implementation. The algorithm is fast when you precompute a table of search alignment jumps for characters matched in certain positions. To me a recursive approach looks conceptually deficient.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    68
    Rep Power
    0
    i didnt understand what you mean..
    ok should i pass str1[10] str2[10] instead of malloc?
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,902
    Rep Power
    481
    Read this program closely, predict the output, run the program. Does it meet your expectation? How is it similar to the program in your post?
    Code:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int main() {
      char*s,*t;
      int n;
      puts("PROGRAM TO ILLUSTRATE INFORMATION LOSS IN YOURS");
      puts("YOU'D EXPECTED THE SAME MESSAGE TO PRINT TWICE.");
      t = s = malloc(999);
      if (NULL == s) exit(0);
      strcpy(s,"Information I want!");
      n = strlen(s);
      puts("DISPLAYING s");
      puts(s);
      s = malloc(999);
      if (NULL == s) { free(t); exit(0); }
      s[n] = 0;
      puts("DISPLAYING s AGAIN");
      puts(s);
      free(t);
      free(s);
      puts("DONE");
      return 0;
    }
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo