Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
February 5th, 2013, 03:01 AM
 swapy
Contributing User

Join Date: Feb 2010
Posts: 67
Time spent in forums: 14 h 44 m 39 sec
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 03:09 AM.

#2
February 5th, 2013, 04:05 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,169
Time spent in forums: 1 Month 3 Weeks 2 Days 10 h 24 m 44 sec
Reputation Power: 455
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!

#3
February 6th, 2013, 02:58 AM
 swapy
Contributing User

Join Date: Feb 2010
Posts: 67
Time spent in forums: 14 h 44 m 39 sec
Reputation Power: 0
i didnt understand what you mean..
ok should i pass str1[10] str2[10] instead of malloc?

#4
February 6th, 2013, 12:29 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,169
Time spent in forums: 1 Month 3 Weeks 2 Days 10 h 24 m 44 sec
Reputation Power: 455
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;
}```

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Boyre moore string comparison