Scribd
Upload
20 views3 pages

Pattern Matching with KMP & Boyer-Moore

The document provides a C program that implements two pattern matching algorithms: Knuth-Morris-Pratt (KMP) and Boyer-Moore. It includes functions for building the longest prefix suffix (LPS) array for KMP and the bad character table for Boyer-Moore, along with a main function to read input text and pattern, and display the results of both searches. The output demonstrates successful pattern matching for the input text 'abracadabra' and pattern 'abra'.

Uploaded by

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

Pattern Matching with KMP & Boyer-Moore

The document provides a C program that implements two pattern matching algorithms: Knuth-Morris-Pratt (KMP) and Boyer-Moore. It includes functions for building the longest prefix suffix (LPS) array for KMP and the bad character table for Boyer-Moore, along with a main function to read input text and pattern, and display the results of both searches. The output demonstrates successful pattern matching for the input text 'abracadabra' and pattern 'abra'.

Uploaded by

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

10.

Implement a Pattern matching algorithms using Boyer- Moore, Knuth-MorrisPratt

Aim: Boyer- Moore, Knuth-MorrisPratt

PROGRAM

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

/* ---------- 1. KNUTH–MORRIS–PRATT ---------- */


static void kmpBuildLPS(const char *pat, int m, int *lps)
/* m = length of pattern
lps[i] = longest proper prefix which is also suffix for pat[0..i] */
{
int len = 0; /* length of previous longest prefix suffix */
lps[0] = 0; /* lps[0] is always 0 */
int i = 1;

while (i < m) {
if (pat[i] == pat[len]) {
++len;
lps[i] = len;
++i;
} else {
if (len != 0)
len = lps[len - 1];
else {
lps[i] = 0;
++i;
}
}
}
}

int kmpSearch(const char *text, const char *pat)


/* returns index of first occurrence, or -1 */
{
int n = (int)strlen(text);
int m = (int)strlen(pat);
if (m == 0) return 0;

int lps[m];
kmpBuildLPS(pat, m, lps);

int i = 0, j = 0; /* i = index for text, j = index for pat */


while (i < n) {
if (text[i] == pat[j]) {
++i; ++j;
if (j == m) return i - j; /* match at i-j */
} else {
if (j != 0)
j = lps[j - 1];
else
++i;
}
}
return -1;
}

/* ---------- 2. BOYER–MOORE (bad-character only) ---------- */


#define ALPHABET 256
static void buildBadChar(const char *pat, int m, int badChar[])
/* badChar[c] = last occurrence of c in pat, 0..ALPHABET-1 */
{
for (int i = 0; i < ALPHABET; ++i) badChar[i] = -1;
for (int i = 0; i < m; ++i) badChar[(unsigned char)pat[i]] = i;
}

int boyerMooreSearch(const char *text, const char *pat)


/* returns index of first occurrence, or -1 */
{
int n = (int)strlen(text);
int m = (int)strlen(pat);
if (m == 0) return 0;

int badChar[ALPHABET];
buildBadChar(pat, m, badChar);

int s = 0; /* shift of pattern with respect to text */


while (s <= n - m) {
int j = m - 1;
while (j >= 0 && pat[j] == text[s + j]) --j;
if (j < 0) return s; /* match at s */

/* shift pattern so that text[s+j] aligns with its last occurrence in pat */
int bcShift = (j - badChar[(unsigned char)text[s + j]]);
s += (bcShift > 1) ? bcShift : 1;
}
return -1;
}

/* ---------- driver ---------- */


int main(void)
{
char text[1024], pat[256];
printf("Text : ");
fgets(text, sizeof(text), stdin);
text[strcspn(text, "\n")] = '\0'; /* strip newline */

printf("Pattern: ");
fgets(pat, sizeof(pat), stdin);
pat[strcspn(pat, "\n")] = '\0';

int kmp = kmpSearch(text, pat);


int bm = boyerMooreSearch(text, pat);

printf("\nKMP result : %s at %d\n",


kmp == -1 ? "not found" : "found", kmp);
printf("BM result : %s at %d\n",
bm == -1 ? "not found" : "found", bm);

return 0;
}

OUTPUT:

Text : abracadabra
Pattern: abra
KMP result : found at 0
BM result : found at 0

You might also like