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數組。同時，記錄最長公共子串的長度和結束位置。最后，根據結束位置和長度，提取出最長公共子串并打印出來。