题解 | #NC127-最长公共子串#

/**

• longest common substring
• @param str1 string字符串 the string
• @param str2 string字符串 the string
• @return string字符串 / /********************************************************************
• 用动态规划求解最长公共子串
• 1、新建1个二维矩阵dp[i][j]，矩阵的行数为str1的长度，列数为str2的长度
• 2、dp[i][j]表示str1第i个字符和str2第j个字符是否相等
• 相等时dp[i][j]为1，不相等时dp[i][j]为0，此时二维矩阵对角线为1的序列即为公共子串
• 为寻找最长公共子串，dp[i][j]还需累加前面对角线字符的个数dp[i-1][j-1]，即dp[i][j]=dp[i-1][j-1]+1
• 如果相等，还需计算前面相等字符的个数，也就是dp[i-1][j-1]，则dp[i][j]=dp[i-1][j-1]+1 ********************************************************************/ char LCS(char str1, char str2 ) { // write code here int str1Len = strlen(str1); int str2Len = strlen(str2); if(str1Len == 0 || str2Len == 0) return NULL;

int length = 0;

int end = 0;
//int dp[str1Len+1][str2Len+1] = {0};
//int (*a)[2]=(int(*)[2])malloc(sizeof(int)*3*2);  
int (*dp)[str2Len] = (int(*)[str2Len])malloc(sizeof(int)*str1Len*str2Len);

for(int i=0; i < str1Len; i++)
{
    for(int j=0; j < str2Len; j++)
    {
        //str1第i个字符和str2第j个字符相等，dp[i][j]根据dp[i-1][j-1]进行累加
        if(str1[i] == str2[j])
        {
            if(i > 0 && j > 0)
                dp[i][j] = dp[i-1][j-1]+1;
            //str1[0]和str2[0]相等
            else
                dp[i][j] = 1;
            
            if(dp[i][j] > length)
            {
                length = dp[i][j];
                end = i;//end记录了最长公共子串最后一个字符在str1中的位置
            }
        }
        //str1第i个字符和str2第j个字符不相等
        else
            dp[i][j] = 0;
    }
}
//遍历完成时，将end+1设为'\0'将str1从最长公共子串之后截断
str1[end+1] = '\0';
//返回最长公共子串在str1中的起始指针
return str1+end-length+1;

}