C如何查找字符串中子字符串个数

在C语言中，查找字符串中子字符串的个数通常可以使用KMP算法（Knuth-Morris-Pratt算法）或者Rabin-Karp算法等高级搜索算法，因为直接遍历可能会有较高的时间复杂度。以下是使用KMP算法的一个简单示例：

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

void compute_lps(char* pattern) {
    int len = strlen(pattern);
    int lps[len];
    lps[0] = 0;
    
    int index = 1;
    while (index < len) {
        if (pattern[index] == pattern[lps[index - 1]]) {
            lps[index] = lps[index - 1] + 1;
            index++;
        } else {
            if (lps[index - 1] != 0) {
                index = lps[index - 1] + 1;
            } else {
                lps[index] = 0;
                index++;
            }
        }
    }
    
    for (int i = 0; i < len; i++) {
        printf("%d ", lps[i]);
    }
}

int kmp_count_substrings(char* text, char* pattern) {
    compute_lps(pattern); // 计算模式串的最长公共前后缀数组
    int count = 0;
    int n = strlen(text), m = strlen(pattern);
    
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) { // 如果当前字符匹配
            i++;
            j++;
            if (j == m) { // 找到一个完整匹配
                count++;
                j = lps[j - 1]; // 如果模式串结束，跳回LPS对应的字符
            }
        } else if (j > 0) { // 如果当前不匹配，尝试从LPS开始回溯
            j = lps[j - 1];
        } else { // 如果模式串的第一个字符不匹配，向右移动文本指针
            i++;
        }
    }
    
    return count;
}

int main() {
    char str[] = "Hello World, Hello Universe";
    char patt[] = "Hello";
    int sub_count = kmp_count_substrings(str, patt);
    printf("Substring '%s' appears %d times in the string.\n", patt, sub_count);
    return 0;
}

在这个例子中，`kmp_count_substrings`函数会返回给定字符串中子串`pattern`出现的次数。