求两个字符串中所有的公共子串c语言

在C语言中，求两个字符串的所有公共子串通常涉及到动态规划算法，其中最著名的是KMP（Knuth-Morris-Pratt）算法或者Boyer-Moore算法。这里以KMP算法为例，它用于查找文本串在主串中的所有非空匹配。

KMP 算法步骤如下：
1. 构建 KMP 自动机（部分前缀最长公共前后缀表），用于快速跳过不匹配的字符。
2. 对于每个主串中的字符，检查其是否与目标子串的当前字符匹配。如果不匹配，则根据机器表更新主串的位置，直到找到匹配或者到达子串的末尾。
3. 如果找到匹配，记录下子串的位置，然后继续寻找下一个公共子串。

以下是简单的KMP算法的C语言代码实现：

#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) {
        while (index > 0 && pattern[index] != pattern[i])
            index = lps[index - 1];
        if (pattern[index] == pattern[i])
            index++;
        lps[i] = index;
    }
}

// 在main_string中查找pattern的所有公共子串
void find_common_substrings(char *text, char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    int lps[m]; // 建立lps数组
    compute_lps(pattern, lps, m);

    for (int i = 0; i <= n - m; ++i) {
        int j;
        for (j = 0; j < m; ++j)
            if (text[i + j] != pattern[j])
                break;

        if (j == m) {
            printf("Substring found at position %d: %s\n", i, pattern);
            // 为了找到所有公共子串，需要从i+m位置开始搜索，因为找到了一个长度为m的公共子串
            i += m - 1;
        } else if (j == 0)
            i++;
    }
}

int main() {
    char text[] = "ABABCAB";
    char pattern[] = "ABC";
    find_common_substrings(text, pattern);
    return 0;
}

运行这个程序，你会看到"ABC"在"text"中的起始位置。注意，这仅找出第一个匹配的子串，如果想找出所有匹配，你需要在循环中稍作调整。