C语言动态规划最长公共子串

C语言中实现动态规划的最长公共子串算法可以通过以下步骤来实现：

1. 定义一个二维数组dp[m+1][n+1]，其中m和n分别为两个字符串的长度。
2. 初始化数组dp的第一行和第一列为0，即dp[i] = dp[j] = 0。
3. 使用两个循环遍历字符串的每个字符，i从1到m，j从1到n。
4. 如果两个字符相等，即str1[i-1] == str2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。
5. 如果两个字符不相等，即str1[i-1] != str2[j-1]，则dp[i][j] = 0。
6. 在循环过程中，记录最大的dp[i][j]值，以及对应的i和j的位置。
7. 循环结束后，最大的dp[i][j]就是最长公共子串的长度。
8. 可以根据最长公共子串的长度和i、j的位置，来获取最长公共子串的具体内容。

以下是一个示例代码：

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

void longestCommonSubstring(char* str1, char* str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    int dp[m+1][n+1];
    int maxLen = 0;
    int maxEndIndex = 0;

    // 初始化dp数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }

    // 计算dp数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; 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];
                    maxEndIndex = i - 1;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    // 获取最长公共子串
    char longestSubstring[maxLen + 1];
    strncpy(longestSubstring, &str1[maxEndIndex - maxLen + 1], maxLen);
    longestSubstring[maxLen] = '\0';

    printf("最长公共子串: %s\n", longestSubstring);
}

int main() {
    char str1[] = "abcdefg";
    char str2[] = "cdefgh";

    longestCommonSubstring(str1, str2);

    return 0;
}

这段代码会输出最长公共子串："cdef"。你可以根据需要修改字符串的内容进行测试。