KMP算法计算串匹配比较次数C语言代码实现

KMP（Knuth-Pratt）算法是一种用于字符串模式匹配的高效算法，它通过构建部分匹配表（也称作失配函数）来避免不必要的字符比较，从而减少了比较次数。下面是C语言实现KMP算法的一个简单版本：

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

// 创建部分匹配表
void compute_lps(char pattern[], int lps[], int len) {
    int index = 0;
    for (int i = 1; i < len; ++i) {
        if (pattern[i] == pattern[index]) {
            lps[i] = index + 1;
            index++;
        } else {
            if (index != 0) {
                index = lps[index - 1];
            } else {
                lps[i] = 0;
            }
        }
    }
}

// 使用KMP算法寻找模式在主串中的位置
int kmp_search(char main_str[], char pattern[]) {
    int len1 = strlen(main_str);
    int len2 = strlen(pattern);
    int lps[len2]; // 部分匹配表
    compute_lps(pattern, lps, len2);

    int index = 0, count = 0;
    while (index < len1) {
        if (main_str[index] == pattern[index]) {
            index++;
            count++;
        } else {
            if (index != 0 && lps[index - 1] != 0) {
                index = lps[index - 1];
            } else {
                main_str[index++] = '\0'; // 如果找不到匹配，结束搜索并回溯
            }
        }
    }

    return count; // 返回匹配次数，如果没有找到匹配则返回0
}

int main() {
    char main_str[] = "ababcabaa";
    char pattern[] = "abca";
    printf("Pattern '%s' occurs %d times in the string.\n", pattern, kmp_search(main_str, pattern));
    return 0;
}

在这个代码中，`compute_lps`函数计算了部分匹配表，而`kmp_search`函数利用这个表在主串中查找模式。注意，如果找到匹配，`count`变量会记录匹配的次数。