Scribd
Upload
27 views2 pages

10 KMP

The document provides a C program that implements the Knuth-Morris-Pratt (KMP) algorithm for string matching. It includes functions to compute the Longest Prefix Suffix (LPS) array and to search for a pattern within a given text. The program prompts the user to input the text and pattern, then outputs the indices where the pattern is found in the text.

Uploaded by

gingergingerginger5555
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
27 views2 pages

10 KMP

The document provides a C program that implements the Knuth-Morris-Pratt (KMP) algorithm for string matching. It includes functions to compute the Longest Prefix Suffix (LPS) array and to search for a pattern within a given text. The program prompts the user to input the text and pattern, then outputs the indices where the pattern is found in the text.

Uploaded by

gingergingerginger5555
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
You are on page 1/ 2

10.

Write a program to solve the string matching problem using KMP algorithm

#include <stdio.h>
#include <string.h>
// Function to compute the Longest Prefix Suffix (LPS) array
void computeLPSArray(char* pat, int M, int* lps) {
int length = 0;
lps[0] = 0; // lps[0] is always 0
int i = 1;
while (i < M) {
if (pat[i] == pat[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}

// KMP search function


void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
i++;
j++;
}
if (j == M) {
printf("Found pattern at index %d\n", i - j);
j = lps[j - 1]; // Look for next possible match
} else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
}

int main() {
char txt[100];
char pat[100];
printf("Enter the text: ");
fgets(txt, sizeof(txt), stdin);
txt[strcspn(txt, "\n")] = 0; // Remove newline character
printf("Enter the pattern: ");
fgets(pat, sizeof(pat), stdin);
pat[strcspn(pat, "\n")] = 0;
KMPSearch(pat, txt);
return 0;
}

output

You might also like