Boyre moore string comparison

Dev Shed Forums Sponsor:

February 5th, 2013, 02:01 AM

swapy

Contributing User

Join Date: Feb 2010

Posts: 66

Time spent in forums: 14 h 4 m
Reputation 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.

February 5th, 2013, 03:05 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,389

Time spent in forums: 1 Month 2 Weeks 3 Days 14 h 22 m 25 sec
Reputation Power: 383

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!

February 6th, 2013, 01:58 AM

swapy

Contributing User

Join Date: Feb 2010

Posts: 66

Time spent in forums: 14 h 4 m
Reputation Power: 0

i didnt understand what you mean..
ok should i pass str1[10] str2[10] instead of malloc?

February 6th, 2013, 11:29 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,389

Time spent in forums: 1 Month 2 Weeks 3 Days 14 h 22 m 25 sec
Reputation Power: 383

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;
}

Boyre moore string comparison

Developer Shed Advertisers and Affiliates