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)。

相关问题

c语言查找两个字符串的最长公共子串

在C语言中，查找两个字符串的最长公共子串可以使用动态规划算法，比如著名的KMP（Knuth-Morris-Pratt）算法或Rabin-Karp算法。其中，KMP算法是一种更为节省空间的方法。

KMP算法的基本思想是利用前缀函数（也叫部分匹配表），计算出模式串中的“坏字符”位置，避免了回溯过程中的无效比较。以下是使用KMP算法的一个简化的示例：

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

// 计算前缀函数
void prefix_function(char* pattern) {
    int len = strlen(pattern);
    int prefix[len];
    for (int i = 1, j = 0; i < len; ++i) {
        while (j > 0 && pattern[i] != pattern[j])
            j = prefix[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        prefix[i] = j;
    }
}

// 查找最长公共子串
char* longest_common_substring(char* str1, char* str2) {
    char* result = "";
    int len1 = strlen(str1), len2 = strlen(str2);
    prefix_function(str2);
    int max_len = 0, end = -1;

    for (int i = 0; i <= len1; ++i) {
        while (str2[end + 1] != str1[i])
            end = prefix[end];
        if (str2[end + 1] == str1[i]) {
            end++;
            int curr_len = i + 1;
            if (curr_len > max_len) {
                max_len = curr_len;
                result = (char*)malloc((max_len + 1) * sizeof(char));
                memcpy(result, str1 + i - max_len + 1, max_len);
                result[max_len] = '\0';
            }
        }
    }

    return result;
}

int main() {
    char str1[] = "ABCDGH";
    char str2[] = "AEDFHR";
    printf("Longest common substring: %s\n", longest_common_substring(str1, str2));
    free(result); // Don't forget to free the memory allocated for 'result'
    return 0;
}

在这个例子中，`prefix_function`计算了`str2`的前缀函数，然后在`longest_common_substring`函数中，我们遍历`str1`，通过`prefix`找到`str2`的匹配部分，更新最长公共子串。

C语言查找两个字符串中的最大公共子串

可以使用动态规划算法来查找两个字符串中的最大公共子串。具体步骤如下：

1. 定义一个二维数组dp，其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。

2. 初始化dp数组，将第一行和第一列都赋值为0。

3. 遍历两个字符串，如果第一个字符串的第i个字符和第二个字符串的第j个字符相等，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = 0。

4. 在遍历的过程中，记录下最长的公共子串的长度和结束位置。

5. 根据结束位置和最长公共子串的长度，可以得到最长公共子串。

以下是示例代码：

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

void findLCS(char *str1, char *str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[len1+1][len2+1];
    int maxLen = 0;
    int endPos = 0;

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endPos = i;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    if (maxLen == 0) {
        printf("没有找到公共子串\n");
    } else {
        printf("最长公共子串为：");
        for (int i = endPos - maxLen; i < endPos; i++) {
            printf("%c", str1[i]);
        }
        printf("\n");
    }
}

int main()
{
    char str1[] = "abcdefg";
    char str2[] = "bcdehij";
    findLCS(str1, str2);
    return 0;
}

输出结果为：

最长公共子串为：bcde