用C语言实现改进的字符串模式匹配的KMP算法。

在C语言中，KMP算法是一种用于高效字符串匹配的技巧，尤其适用于处理长文本和重复模式的情况。Knuth-Morris-Pratt (KMP) 算法通过预计算模式串的失配函数（部分匹配表或失步数组），避免了在每次比较字符失败时都回溯整个模式。

以下是简单的C语言实现步骤：

1. 定义部分匹配表（失步数组）：

int* create_lps(char pattern[], int len) {
    int lps[len + 1], i = 0, j = -1;
    lps[0] = 0;
    while (i < len - 1) {
        if (pattern[i] == pattern[j + 1]) {
            lps[i + 1] = j + 1;
            i++;
            j++;
        } else if (j != -1) {
            j = lps[j];
        } else {
            lps[i + 1] = 0;
            i++;
        }
    }
    return lps;
}

2. 主搜索函数：

int kmp_search(char text[], char pattern[], int text_len, int pattern_len, int lps[]) {
    int i = 0, j = 0;
    while (i < text_len && j < pattern_len) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    if (j == pattern_len) {
        return i - j; // 如果找到匹配，则返回起始位置
    } else {
        return -1; // 没有找到匹配
    }
}

3. 使用部分匹配表进行实际搜索：

int main() {
    char text[] = "ababcabaa";
    char pattern[] = "abca";
    int lps = create_lps(pattern, strlen(pattern));
    int match_pos = kmp_search(text, pattern, strlen(text), strlen(pattern), lps);
    if (match_pos != -1)
        printf("Pattern found at index %d\n", match_pos);
    else
        printf("Pattern not found in the text.\n");
    return 0;
}