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

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

int main() {
    
    char sht[310] = {0};
    char lon[310] = {0};

    gets(sht);
    gets(lon);
    if(strlen(sht) > strlen(lon))
    {
        char tmp[310] = {0};
        strcpy(tmp, sht);
        strcpy(sht, lon);
        strcpy(lon, tmp);
    }

    int len_sht = strlen(sht);
    int len_lon = strlen(lon);
    int dp[len_sht][len_lon];
    memset(dp, 0, sizeof(int)*len_sht*len_lon);

    int p_sht = 0;
    int p_lon = 0;
    int max = 0;
    int end = 0;
    //初始首行
    for(; p_lon < len_lon; ++ p_lon)
    {
        if(sht[0] == lon[p_lon])
        {
            dp[0][p_lon] = 1;
        }
        else {
            dp[0][p_lon] = 0;
        }
    }
    //初始首列
    for(p_lon = 0, p_sht = 0; p_sht < len_sht; ++ p_sht)
    {
        if(sht[p_sht] == lon[0])
        {
            dp[p_sht][0] = 1;
        }
        else {
            dp[p_sht][0] = 0;
        }
    }

    for(p_sht = 1; p_sht < len_sht; ++ p_sht)
    {
        for(p_lon = 1; p_lon < len_lon; ++ p_lon)
        {
            if(sht[p_sht] == lon[p_lon])
            {
                dp[p_sht][p_lon] = dp[p_sht-1][p_lon-1] + 1;
            }
            else {
                dp[p_sht][p_lon] = 0;
            }
        }
    }

    for(p_sht = 0; p_sht < len_sht; ++ p_sht)
    {
        for(p_lon = 0; p_lon < len_lon; ++ p_lon)
        {
            if(max < dp[p_sht][p_lon])
            {
                max = dp[p_sht][p_lon];
                end = p_sht;
            }
        }
    }

    for(int i = end - max + 1; i <= end; ++ i)
    {
        putchar(sht[i]);
    }

    return 0;
}