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

//学习了大佬的解法，自己也理解了一下，稍微理解了一点动态规划
//最重要的是设置状态，设置dp[i][j]为以str1[i - 1] 和 str2[j - 1]为终点的公共子串长度



#include <stdio.h>

int main() {
    char *str1 = (char *)malloc(301);
    char *str2 = (char *)malloc(301);
    scanf("%s %s", str1, str2);
    int m = strlen(str1);
    int n = strlen(str2);
    if(m > n)
    {
        int tmp = m;
        m = n;
        n = tmp;
        char str_tmp[301] = {0};
        strcpy(str_tmp, str1);
        strcpy((str1), str2);
        strcpy(str2, str_tmp);
    }
    int dp[301][301] = {0}; //dp[i][j]代表以str1[i - 1] 和 str2[j - 1]为终点的公共子串长度
    int i = 1;
    int j = 1;
    int maxlen = 0;
    int index = 0;
    for(i = 1; i <= m; i++)
    {
        for(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];
                    index = i - 1;
                }
            }
            else {
                dp[i][j] = 0; /*str1[i - 1] != str2[j - 1]则代表以str1[i - 1] 和 
                                str2[j - 1]为终点的公共子串长度为0*/
            }
        }
    }
    for(int k = index - maxlen + 1; k <= index; k++)
    {
        printf("%c", str1[k]);
    }

    return 0;
}