kmp算法求出现次数的c程序，两个字符串

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串中查找给定模式串的所有出现位置。以下是使用C语言实现KMP算法计算模式串在主串中出现次数的一个简单示例：

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

// 计算前缀函数
void compute_prefix_function(char pattern[], int prefix[]) {
    int len = strlen(pattern);
    int j = 0;

    for (int i = 1; i < len; i++) {
        while (j > 0 && pattern[i] != pattern[j])
            j = prefix[j - 1];
        
        if (pattern[i] == pattern[j])
            j++;
            
        prefix[i] = j;
    }
}

// KMP算法寻找模式串在主串中的出现次数
int kmp_search(char text[], char pattern[]) {
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    int count = 0;
    int index = 0;
    int prefix[pattern_len];

    compute_prefix_function(pattern, prefix);

    while (index < text_len) {
        if (text[index] == pattern[0]) {
            int j = 1;
            while (j < pattern_len && text[index + j] == pattern[j]) {
                j++;
            }

            if (j == pattern_len) {
                count++;
                index += j;
            } else {
                if (prefix[j - 1] != 0)
                    index = index + prefix[j - 1] + 1;
                else
                    index++;
            }
        } else {
            index++;
        }
    }

    return count;
}

int main() {
    char str[] = "ABABCABABABC";
    char pat[] = "ABC";

    printf("Pattern '%s' appears %d times in the string.\n", pat, kmp_search(str, pat));
    return 0;
}

在这个程序中，首先计算了模式串的前缀函数，然后在主串中逐个检查每个字符是否匹配模式，如果不匹配，则通过前缀函数找到跳过的位置继续搜索。