Pattern Matching Algorithm in C

Pattern matching algorithms are used to search for occurrences of a specific pattern (subsequence) within a larger sequence (text). One of the most well-known pattern matching algorithms is the Knuth-Morris-Pratt (KMP) algorithm. The KMP algorithm efficiently searches for occurrences of a pattern in linear time.

Here’s an implementation of the Knuth-Morris-Pratt algorithm in C:

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

void computeLPSArray(char *pattern, int m, int *lps) {
    int length = 0;
    lps[0] = 0; // lps[0] is always 0

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

void KMPSearch(char *text, char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);

    int lps[m];
    computeLPSArray(pattern, m, lps);

    int i = 0; // Index for text[]
    int j = 0; // Index for pattern[]

    while (i < n) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == m) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";

    printf("Text: %s\n", text);
    printf("Pattern: %s\n", pattern);

    KMPSearch(text, pattern);

    return 0;
}

This implementation of KMP searches for occurrences of the pattern in the given text and prints the starting indices of each occurrence.

Remember that the Knuth-Morris-Pratt algorithm is just one of several pattern matching algorithms available. Depending on your specific requirements and the characteristics of your data, you might consider other algorithms like the Boyer-Moore algorithm or the Rabin-Karp algorithm as well.