查找两个字符串中的最大公共子串，C语言请使用至少三种方法实现

1. 动态规划法：

定义一个二维数组dp[i][j]，表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。初始化dp[i][j]为0，然后遍历两个字符串，如果第一个字符串的第i个字符和第二个字符串的第j个字符相同，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。最后遍历dp数组，找到最大值即为最长公共子串的长度。

2. 滑动窗口法：

定义两个指针i和j，分别指向两个字符串的开头，然后移动j指针，如果第一个字符串中包含第二个字符串中的字符，则移动i指针，直到不包含为止。每次移动i指针时，记录当前的最长公共子串的长度，最后找到最大值即可。

3. 后缀数组法：

将两个字符串拼接起来，并在相邻的字符串之间插入一个特殊字符，然后构建后缀数组。然后遍历后缀数组，找到相邻两个后缀的最长公共前缀，最后找到最大值即为最长公共子串的长度。

相关问题

求两个字符串中所有公共子串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`函数则打印出所有的公共子串。

C语言 查找两个字符串中的最大公共子串，三种方法实现

1. 暴力枚举法：对于两个字符串中的每一个子串，判断是否在另一个字符串中出现，时间复杂度为O(n^3)。

2. 动态规划法：定义一个二维数组dp[i][j]表示以第一个字符串中第i个字符和第二个字符串中第j个字符结尾的最长公共子串的长度，然后根据状态转移方程dp[i][j] = dp[i-1][j-1] + 1或者dp[i][j] = 0，时间复杂度为O(n^2)。

3. 后缀数组法：将两个字符串拼接起来，中间用一个特殊字符隔开，然后求出后缀数组和height数组，height[i]表示排名为i和i-1的后缀的最长公共前缀的长度，然后找到height数组中的最大值即可，时间复杂度为O(nlogn)。