Aim:

Write a program to Implement a Pattern matching algorithms using Boyer- Moore

Solution :

C program to Implement a Pattern matching algorithms using Boyer- Moore

#include <stdio.h>
#include <string.h>

int max(int a, int b)
{
    if(a > b)
		return a;
    else
		return b;
}
int boyermorre(char p[],char t[])
{
    int bctable[128],i,j,k;
    int n = strlen(t);
    int m = strlen(p);
    for(j=0; j<128; j++)
    {
        bctable[j]=m;
    }
    for(j=0; j<m; j++)
    {
        k=(int)p[j];
        bctable[k]=m-j-1;
    }
    i=m-1;
    while(i < n)
    {
        j=m-1;
        while(j >= 0 && p[j] == t[i])
        {
            i--;
            j--;
        }
        if(j == -1)
            return i+1;
        i = i + max((int)bctable[t[i]],m-j);
    }
    return 0;
}


int main() {
   char t[]="kiss*miss*in*mississippi";
   char p[]="missi";
   int i;
   i=boyermorre(p,t);
   if(i)
		printf("pattern is present in text at position %d",i+1);
   else
		printf("pattern is not present in text");
   return 0;
}

pattern is present in text at position 14

Related Content :

Data Structures Lab Programs

1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

4) Write a program that implement Stack (its operations) using Array View Solution

5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution

6) Write a program that implement Queue(its operations) using Array View Solution

7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution

8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution

9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution

10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution

11) Write a program to implement the tree traversal methods using Recursive View Solution

12) Write a program to implement the tree traversal methods using Non Recursive View Solution

13) Write a program to implement Binary Search Tree (its operations) View Solution

14) Write a program to implement AVL Tree (its operations) View Solution

15) Write a program to implement Red - Black Tree (its operations) View Solution

16) Write a program to implement B Trees (its operations) View Solution

17) Write a program to implement B+ Trees (its operations) View Solution

18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution

19) Write a program to implement the graph traversal methods (Depth First Search) View Solution

20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution

21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution