华为机试-查找两个字符串a,b中的最长公共子串（HJ65）-纯C

纯C

啊，我终于真正学会了动态规划

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

#define MAX 1500

int main()
{
    int dp[MAX][MAX] = {0};
    char str1[MAX] = {'\0'}, str2[MAX] = {'\0'};
    while(gets(str1))
    {
        gets(str2);
        int len1=strlen(str1), len2=strlen(str2);
        //str1保存短字符串
        if(len1 > len2)
        {
            char temp[MAX] = {'\0'};
            strcpy(temp, str1);
            strcpy(str1, str2);
            strcpy(str2, temp);
            len1 += len2;
            len2 = len1 - len2;
            len1 = len1 - len2;
        }
        //maxlen记录最长公共字串长度，index记录第一个最长字串的最后一个字符位置
        int maxlen=0, index;
        for(int i=0; i<len1; i++)
        {
            for(int j=0; j<len2; j++)
            {
                if(str1[i] == str2[j])
                {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    if(maxlen < dp[i+1][j+1])
                    {
                        maxlen = dp[i+1][j+1];
                        index = i;
                    }
                }
                else
                {
                    dp[i+1][j+1] = 0;
                }
            }
        }
        char out[MAX] = {'\0'};
        strncpy(out, &str1[index-maxlen+1], maxlen);
        printf("%s\n", out);
    }
    return 0;
}