LCS（最长公共子串）系列问题-蒲公英云

LCS（最长公共子串）系列问题

问题一

探索递归模式下，电脑最长计算的长度情况。（我也很神秘，为什么老师要出这种问题。。。）

就是不断修改下面的n，来看看数值就知道了~

#include <iostream>
using namespace std;
#include <string>
string multiply(string s, int time) { 
    string t;
    for (int i = 0; i < time; ++i) t = t + s;
    return t;
}
string x, y;
int lcs(int i, int j) { 
    if (i == 0 || j == 0) return 0;
    if (x[i] == y[j]) return lcs(i - 1, j - 1) + 1;
    int temp1 = lcs(i - 1, j);
    int temp2 = lcs(i, j - 1);
    if (temp1 > temp2) return temp1;
    return temp2;
}
int main() { 
    x = "123";
    y = "12";
    int n = 16;
    x = multiply(x, n);
    y = multiply(y, n);
    cout << lcs(x.length(), y.length()) << endl;
    system("pause");
}

递推实现，并输出路径

#include <iostream>
using namespace std;
#include <string>
int lcs(string A, string B, string &C, int n, int m) { 
    int i, j, k;
    int **L = new int*[n + 1];
    for (i = 0; i <= n; ++i) L[i] = new int[m + 1];
    int **S = new int*[n + 1];
    for (i = 0; i <= n; ++i) S[i] = new int[m + 1];
    for (i = 0; i <= n; ++i) L[i][0] = 0;
    for (j = 0; j <= m; ++j) L[0][j] = 0;
    for (i = 1; i <= n; ++i) { 
        for (j = 1; j <= m; ++j) { 
            if (A[i-1] == B[j-1]) { 
                L[i][j] = L[i - 1][j - 1] + 1;
                S[i][j] = 1;
            }
            else if (L[i - 1][j] >= L[i][j - 1]) { 
                L[i][j] = L[i - 1][j];
                S[i][j] = 2;
            }
            else { 
                L[i][j] = L[i][j - 1];
                S[i][j] = 3;
            }
        }
    }
    k = L[n][m];
    C = "";
    for (i = 0; i < k; ++i) C.append("0");
    i = n, j = m;
    while (i != 0 && j != 0) { 
        switch (S[i][j])
        { 
        case 1:
            C[k-1] = A[i-1]; i--; j--; k--; break;
        case 2:
            i--; break;
        case 3:
            j--; break;
        }
    }
    int ans = L[n][m];
    for (i = 0; i <= n; ++i) delete L[i];
    delete[] L;
    for (i = 0; i <= n; ++i) delete S[i];
    delete[] S;
    return ans;
}
int main() { 
    string X = "bcdbadce", Y = "cabdcbc", Z="";
    cout << lcs(X, Y, Z, X.length(), Y.length()) << endl;
    cout << Z << endl;
    system("pause");
}

输出：

4
bcbc

思路其实很简单，按照之前做的划分方式就好了。

难点： 在于为什么写为A[i-1] = = B[i-1] 还有就是后面有一个C[k-1] = A[i-1];

解释： 因为全局的i , j都是表示的前面还有多个剩余串数量，也就是是index +1 所以这里定位回去到index的时候，就需要减一了。

问题三

递归式的，但是要求输出序列。

#include <iostream>
using namespace std;
#include <string>
typedef pair<string, int> DATA;
string X = "bcdbadce", Y = "cabdcbc";
DATA lcs(int i, int j) { 
    if (i == 0 || j == 0) return { "", 0};
    if (X[i-1] == Y[j-1]) {  
        DATA temp = lcs(i - 1, j - 1);
        temp.first.push_back(X[i-1]);
        temp.second++;
        return temp;
    }
    DATA temp1 = lcs(i - 1, j);
    DATA temp2 = lcs(i, j - 1);
    if (temp1.second >= temp2.second) return temp1;
    return temp2;
}
int main() { 
    DATA temp = lcs(X.length(), Y.length());
    cout << temp.first << "\n" << temp.second << endl;
    system("pause");
}