阅读背景:

最长公共子序列VS最长连续公共子序列

来源:互联网 
int findLCS(string A, int n, string B, int m) {// 最长公共子序列
    string strA = "#" + A;
    string strB = "#" + B;
    int C[n+1][m+1];
    for(int i=0; i <= n; i++)
        C[i][0] = 0;
    for(int i=0; i <= m; i++)
        C[0][i] = 0;
    for(int i=1; i <= n; i++) {
        for(int j=1; j <= m; j++) {
            if(strA[i] == strB[j])
                C[i][j] = C[i-1][j-1] + 1;
            else if(C[i-1][j] > C[i][j-1])
                C[i][j] = C[i-1][j];
            else
                C[i][j] = C[i][j-1];
        }
    }
    return C[n][m];
}

int findLongest(string A, int n, string B, int m) {// 最长连续公共子序列
    string strA = "#" + A;
    string strB = "#" + B;
    int C[n+1][m+1];
    for(int i=0; i <= n; i++)
        C[i][0] = 0;
    for(int i=0; i <= m; i++)
        C[0][i] = 0;
    int maxL = -1;
    for(int i=1; i <= n; i++) {
        for(int j=1; j <= m; j++) {
            if(strA[i] == strB[j])
                C[i][j] = C[i-1][j-1] + 1;
            else
                C[i][j] = 0;
            if(C[i][j] > maxL)
                maxL = C[i][j];
        }
    }
    return maxL;
}int findLCS(string A, int n, string B, int m) {



你的当前访问异常,请进行认证后继续阅读剩余内容。

分享到: