Character strings are linear data structures composed of sequentially connected characters, built on standard linear table implementations. Two core algorithms for matching a pattern string within a main string are covered here: Brute-Force (BF) and Knuth-Morris-Pratt (KMP).

Brute-Force (BF) Matching Algorithm

This implementation uses 1-indexed array storage, where the 0th index stores the total length of the string for quick lookup. The BF algorithm compares characters one by one: when a mismatch occurs, reset the pattern string's index to the first position, and move the main string's index back to the position immediately after the first character of the current matching attempt.

typedef struct {
    int length;
    char chars[100];
} SString;

int bruteForceMatch(SString mainStr, SString pattern, int startPos) {
    int i = startPos;
    int j = 1;
    while (i <= mainStr.length && j <= pattern.length) {
        if (mainStr.chars[i] == pattern.chars[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > pattern.length) {
        return i - pattern.length;
    }
    return 0;
}

KMP Matching Algorithm

The KMP algorithm optimizes the BF approach by eliminating backtracking of the main string's pointer. Instead, it uses a precomputed next array to adjust the pattern srting's pointer based on partial matching results, avoiding redundant character comparisons.

First, the function to generate the standard next array:

void computeNextArray(SString pattern, int next[]) {
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i < pattern.length) {
        if (j == 0 || pattern.chars[i] == pattern.chars[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
}

Next, the core KMP matching function:

int kmpMatch(SString mainStr, SString pattern, int startPos) {
    int i = startPos;
    int j = 1;
    int next[100];
    computeNextArray(pattern, next);
    while (i <= mainStr.length && j <= pattern.length) {
        if (j == 0 || mainStr.chars[i] == pattern.chars[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > pattern.length) {
        return i - pattern.length;
    }
    return 0;
}

Too further optimize the next array, we can create a nextVal array that skips redundant checks when the current pattern character matches the character at the position pointed to by the satndard next array:

void computeOptimizedNextArray(SString pattern, int nextVal[]) {
    int i = 1;
    int j = 0;
    nextVal[1] = 0;
    while (i < pattern.length) {
        if (j == 0 || pattern.chars[i] == pattern.chars[j]) {
            nextVal[++i] = ++j;
        } else {
            j = nextVal[j];
        }
    }
    for (int k = 2; k <= pattern.length; k++) {
        if (pattern.chars[k] == pattern.chars[nextVal[k]]) {
            nextVal[k] = nextVal[nextVal[k]];
        }
    }
}