C语言字符串中的最长公共子串

在C语言中，要找到两个字符串中的最长公共子串，可以使用动态规划算法

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

void longestCommonSubstring(char *str1, char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int maxLength = 0;
    int endIndex = -1;

    // 创建一个二维数组，用于存储动态规划的结果
    int dp[len1 + 1][len2 + 1];

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

    if (maxLength == 0) {
        printf("没有公共子串\n");
    } else {
        char result[maxLength + 1];
        strncpy(result, &str1[endIndex - maxLength + 1], maxLength);
        result[maxLength] = '\0';
        printf("最长公共子串: %s\n", result);
    }
}

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

这个程序首先计算两个输入字符串的长度，然后创建一个二维数组dp来存储动态规划的结果。接下来，遍历两个字符串，如果当前字符相等，则更新dp数组。同时，记录最长公共子串的长度和结束位置。最后，根据结束位置和长度，提取出最长公共子串并打印出来。