题解 | #查找两个字符串a,b中的最长公共子串#

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

int main()
{
    char str1[308], str2[308], temp[308];
    scanf("%s%s", str1, str2);
    int len1 = strlen(str1), len2 = strlen(str2), i, j, commonlen = 0, index = -1, t, flag = 0;
    if(len2 < len1){
        strcpy(temp, str1);
        strcpy(str1, str2);
        strcpy(str2, temp);
        t = len1;
        len1 = len2;
        len2 = t;
    }
    int dp[len1][len2];
    memset(dp, 0, sizeof(int) * len1 * len2);
    for(i = 0; i < len1; i++){
        if(str1[i] == str2[0]){
            dp[i][0] = 1;
            if(dp[i][0] > commonlen){
                commonlen = 1;
                index = i;
            }
        }
    }
    for(i = 0; i < len2; i++){
        if(str2[i] == str1[0]){
            dp[0][i] = 1;
            if(commonlen == 0){
                commonlen = 1;
                flag = 1;
            }
        }
    }
    for(i = 1; i < len1; i++){
        for(j = 1; j < len2; j++){
            if(str1[i] == str2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > commonlen){
                    commonlen = dp[i][j];
                    index = i;
                }
            }
        }
    }
    if(flag == 1 && commonlen == 1){
        printf("%c", str1[0]);
    }
    else{
        if (index >= 0){
            for(i = index - commonlen + 1; i <= index; i++){
                printf("%c", str1[i]);
            }
        }
    }
    printf("\n");
    return 0;
}