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

在C语言中，求两个字符串的所有公共子串通常涉及到动态规划（Dynamic Programming）。你可以使用KMP算法（Knuth-Morris-Pratt Algorithm）或者Boyer-Moore算法，其中KMP算法更适用于查找最长公共前缀。

以下是使用KMP算法的一个简单示例：

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

void compute_lps(char *pattern) {
    int len = strlen(pattern), lps[256];
    lps[0] = 0;
    int i = 1;
    while (i < len) {
        if (pattern[i] == pattern[lps[i - 1]])
            lps[i++] = lps[i - 1] + 1;
        else {
            if (lps[i - 1] != 0)
                i = lps[i - 1];
            else
                lps[i++] = 0;
        }
    }
    // lps[] now contains the longest proper prefix which is also suffix
    // for every substring of pattern
}

int kmp_search(char *text, char *pattern) {
    int m = strlen(text);
    int n = strlen(pattern);
    compute_lps(pattern);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (pattern[j] == text[i])
            j++;
        else if (j > 0)
            j = lps[j - 1];
        else
            i++;
    }
    if (j == n) // found a match
        return i - n;
    else
        return -1;
}

// Function to print all common substrings
void print_common_substrings(char *text, char *pattern) {
    int index = kmp_search(text, pattern);
    if (index == -1)
        printf("No common substring\n");
    else {
        while (index > 0) {
            printf("%s\n", &text[index]);
            index = kmp_search(text + index + 1, pattern);
        }
    }
}

int main() {
    char str1[] = "ABABC";
    char str2[] = "BABCA";
    print_common_substrings(str1, str2);
    return 0;
}

在这个例子中，`compute_lps`函数计算模式串的局部匹配表，`kmp_search`函数用于查找模式串在文本串中的位置，`print_common_substrings`函数则打印出所有的公共子串。