Scribd
Upload
41 views3 pages

Implementation of Boyer Moore Algorithm

Uploaded by

tosoumalya.svist
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views3 pages

Implementation of Boyer Moore Algorithm

Uploaded by

tosoumalya.svist
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Implementation of Boyer Moore Algorithm

Soumalya De
Paper Name: Advance Data Structure

Department: CSE

Date:25/11/2021

Implement the Boyer Moore algorithm using C.

Solution:
# include <stdio.h>

# include <limits.h>

# include <string.h>

# define NO_OF_CHARS 256

int max (int a, int b) { return (a > b)? a: b; }

void badCharHeuristic( char *str, int size,

int badchar[NO_OF_CHARS])

int i;

for (i = 0; i < NO_OF_CHARS; i++)

badchar[i] = -1;

for (i = 0; i < size; i++)

badchar[(int) str[i]] = i;

void search( char *txt, char *pat)

{
int m = strlen(pat);

int n = strlen(txt);

int badchar[NO_OF_CHARS];

badCharHeuristic(pat, m, badchar);

int s = 0;

while(s <= (n - m))

int j = m-1;

while(j >= 0 && pat[j] == txt[s+j])

j--;

if (j < 0)

printf("\n pattern occurs at shift = %d", s);

s += (s+m < n)? m-badchar[txt[s+m]] : 1;

else

s += max(1, j - badchar[txt[s+j]]);
}

int main()

char txt[] = "ABACBCABCDABBACABC";

char pat[] = "ABC";

search(txt, pat);

return 0;

Output:
pattern occurs at shift = 6

pattern occurs at shift = 15

You might also like