题解 | #最长公共子串#

char* LCS(char* str1, char* str2 ) {
    int len1=strlen(str1);
    int len2=strlen(str2);
    //初始化一个len1+1和len2+1大小的二维数组，+1是为了避免判断边界条件
    int dp[len1+1][len2+1];
    //将多出的一行一列初始化为0
    for(int i=0;i<len1+1;i++){
        dp[i][0]=0;
    }
    for(int j=0;j<len2+1;j++){
        dp[0][j]=0;
    }
    
    int max_len=0;
    int end=0;
    //因为dp矩阵多一行一列，所以索引从1开始，后面有关索引的都要注意转换的关系
    for(int i=1;i<len1+1;i++){
        for(int j=1;j<len2+1;j++){
            if(str1[i-1]==str2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=0;
            }
            if(dp[i][j]>max_len){
                max_len=dp[i][j];
                end=i;
            }
        }
    }
    str1[end]='\0';
    
    return str1+end-max_len;
}