题解 | #最长公共子串#

/*写得很垃圾，总体思路就是当str1[i-1]==str2[j-1]时dp[i][j]=dp[i-1][j-1]+1,当不相等时dp[i][j]=0，然后用Max表示最大子串，s1表示最大子串时对应str2时所指向的字符即str2[j-1],然后向前倒退Max个字符就是子串，用数组保存返回即可*/
/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
 int dp[5001][5001];
 char b[5001];
char* LCS(char* str1, char* str2 ) 
{
    int len1 = strlen(str1),len2 = strlen(str2),i,j;
    long Max = 0;
    int s1=0;
    for(i=1;i<=len1;i++)
    {
        for(j=1;j<=len2;j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                dp[i][j] = dp[i-1][j-1]+1;
                if(dp[i][j]>Max)
                {
                    Max = dp[i][j];
                    s1 = j;
                }
            }
            else
            dp[i][j] = 0;
        }
    }
    b[Max]=0;
    while(Max)
    {
        b[Max-1]=str2[s1-1];
        Max--;
        s1--;

    }
    return b;
    // write code here
}