最长公共子串

char* LCS(char* s1, char* s2 ) {
    int dp[10000][10000], i, j, maxLen=0, maxS1_i=0;
    char *res;
    res = (char*)malloc((strlen(s1)<strlen(s2)?strlen(s1):strlen(s2))+1);
    strcpy(res, ""); 
    for(i=0; i<=strlen(s1); i++) 
        dp[i][0] = (s2[i]==s1[0] ? 1 : 0);
    for(i=0; i<=strlen(s2); i++) 
        dp[0][i] = (s1[i]==s2[0] ? 1 : 0);
    for(i=1; i<strlen(s1); i++) {
        for(j=1; j<strlen(s2); j++) {
            if(s1[i]==s2[j]) {
                dp[i][j] = dp[i-1][j-1]+1;
                if(maxLen<dp[i][j]) {
                    maxLen = dp[i][j];
                    maxS1_i = i;
                }
            }
            else 
                dp[i][j] = 0;
        }
    }
    strncpy(res, s1+maxS1_i-maxLen+1, maxLen);
    res[maxLen] = 0;
    return res;
}

/*
暴力，双层循环检索是否匹配，匹配则继续下一索引匹配，直到遇到不同字符串。
更新最大公共子串的长度与起始位置。
全部找完后，将最大公共子串复制到返回字符串中。
*/
char* LCS2(char* str1, char* str2 ) {
    // write code here
    char* res = (char*)malloc(sizeof(char)*5000);
    memset(res, 0, sizeof(char)*5000);
    int len1 = strlen(str1), len2 = strlen(str2);
    int n = 0;
    int maxStart = 0, maxN = 0;

    for(int i=0; i<len1; i++){
        for(int j=0; j<len2; j++){
            //注意一定要判断索引是否有效，排查了很久才发现索引超出有效范围。
            while(i+n < len1 && j+n < len2 && str1[i+n] == str2[j+n])n++;  //此处每次都需要遍历，是动规优化的点 
            if(n>maxN){
                maxN = n;
                maxStart = i;
            }
            n=0;
        }
    }
    memcpy(res, &str1[maxStart], sizeof(char)*maxN);

    return res;
}

//动态规划：节省暴力的多次遍历。
//使用上一次的状态即dp[i-1][j-1]来更新当前位置的匹配长度
char* LCS(char* str1, char* str2 ) {
    // write code here
    int maxN = 0, maxEnd = 0;   //此处为maxEnd，即匹配的最后一个字符位置
    char* res = (char*)malloc(sizeof(char)*5000);
    memset(res, 0, sizeof(char)*5000);
    int len1 = strlen(str1), len2 = strlen(str2);
    int dp[len1][len2];
    memset(dp, 0, sizeof(int)*len1*len2);
    for(int i=0; i<len1; i++){
        for(int j=0; j<len2; j++){
            if(str1[i] == str2[j]){ //匹配上
                if(i==0 || j==0){   //如果是边沿，则置1
                    dp[i][j] = 1;
                }else{              //如果不是边沿，则取左上角的dp，来更新最长匹配长度
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                
            }
            if(maxN < dp[i][j]){    //更新最长字符串的信息
                maxN = dp[i][j];
                maxEnd = i;
            }
        }
    }
    //此处由于是maxEnd，因此需要通过maxEnd-maxN+1来获取匹配字符串的开头位置
    memcpy(res, &str1[maxEnd-maxN+1], sizeof(char)*maxN);
    return res;
}

//动态规划
char* LCS(char* str1, char* str2 ) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int maxlen = 0, index;
    int (*dp)[len2] = (int (*)[len2])calloc(len1 * len2, sizeof(int));
    for(int i = 0; i < len1; i++) { //初始化
        if(str2[0] == str1[i]) {
            dp[i][0] = 1;
            maxlen = 1;
            index = i;
        }
    }
    for(int i = 0; i < len2; i++) { //初始化
        if(str1[0] == str2[i]) {
            dp[0][i] = 1;
            maxlen = 1;
            index = 0;
        }
    }
    for(int i = 1; i < len1; i++) {
        for(int j = 1; j < len2; j++) {
            if(str1[i] == str2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1; //状态转移表达式
                if(dp[i][j] > maxlen) {
                    maxlen = dp[i][j];
                    index = i;
                }
            }
        }
    }
    char *str = (char *)calloc(maxlen+1, sizeof(char));
    memcpy(str, str1+(index - maxlen + 1), maxlen); //从str1上拷贝最长公共子串
    return str;
}