【算法】求两字符串最长公共子序列——动态规划

“两字符串最长公共子序列”的概念：

一个字符串的子序列，是指从该字符串中去掉任意多个字符后剩下的字符在不改变顺序的情况下组成的新字符串。这个子序列是可以不连续的。最长公共子序列，是指多个字符串可具有的长度最大的公共的子序列。举个例子，如：有两条随机序列，如$ 1 3 4 5 5 $和$ 2 4 5 5 7 6$，则它们的最长公共子序列便是：$4 5 5$。

注意最长公共子串和最长公共子序列的区别:

最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

解决思路

（1）穷举法

解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对$X$的每一个子序列，检查它是否也是$Y$的子序列，从而确定它是否为$X$和$Y$的公共子序列，并且在检查过程中选出最长的公共子序列。$X$和$Y$的所有子序列都检查过后即可求出$X$和$Y$的最长公共子序列。$X$的一个子序列相应于下标序列{$1, 2, …, m$}的一个子序列，因此，$X$共有$2^m$个不同子序列（$Y$亦如此，如为$2^n$），从而穷举搜索法需要指数时间（$2^m * 2^n$）。

（2）动态规划算法

最长公共子序列问题也有最优子结构性质。记:

$X_i$=<$x_1，⋯，x_i$>，即$X$序列的前$i$个字符 ($1≤i≤m$)（前缀）
$Y_j$=<$y_1，⋯，y_j$>，即$Y$序列的前$j$个字符 ($1≤j≤n$)（前缀）
假定$Z$=<$z_1，⋯，z_k$> $∈ LCS(X,Y)$,那么不难有以下结论：

（1）若$x_m=y_n$（最后一个字符相同），则不难用反证法证明：该字符必是$X$与$Y$的任一最长公共子序列$Z$（设长度为$k$）的最后一个字符，即有$z_k = x_m = y _n$ 且显然有 $Z _{k-1}∈LCS(X _{m-1}, Y _{n-1})$即$Z$的前缀$Z _{k-1}$是$X _{m-1}$与$Y _{n-1}$的最长公共子序列。此时，问题化归成求$X _{m-1}$与$Y _{n-1}$的$LCS$（$LCS(X , Y)$的长度等于$LCS(X _{m-1} , Y _{n-1})$的长度加1）。

（2）若$x _m≠y _n$，则亦不难用反证法证明：要么$Z∈LCS(X _m-1, Y)$，要么$Z∈LCS(X , Y _n-1)$。由于$z _k≠x _m$与$z _k≠y _n$其中至少有一个必成立，若$z _k≠x _m$则有$Z∈LCS(X _{m-1} , Y)$，类似的，若$z _k≠y _n$ 则有$Z∈LCS(X , Y _{n-1})$。此时，问题化归成求$X _{m-1}$与$Y$的$LCS$及$X$与$Y _{n-1}$的$LCS$。$LCS(X , Y)$的长度为：$max\lbrace LCS(X _{m-1} , Y)的长度, LCS(X , Y _{n-1})的长度\rbrace $。 从上面的分析可以看出，解决这个层次的LCS问题，要求三个方面的东西：
$$ A：LCS（X _{m-1}，Y _{n-1}）+1； $$ $$ B：LCS（X _{m-1}，Y），LCS（X，Y _{n-1}）；
$$ $$ C：max\lbrace LCS（X _{m-1}，Y），LCS（X，Y _{n-1}）\rbrace 。
$$

算法实现

（1）穷举法递归实现

//1.穷举法：递归实现
int LCS(string x, string y, char* result, int xlen, int ylen, int relen, int i, int j){
    if(i < xlen && j < ylen){
        if(x[i] == y[j]){
            result[relen] = x[i];
            relen++;
            return 1 + LCS(x, y, result, xlen, ylen, relen, i+1, j+1);
        }else{
            int count_1 = LCS(x, y, result, xlen, ylen, relen, i, j + 1);
            int count_2 = LCS(x, y, result, xlen, ylen, relen, i + 1, j);
            return count_1 > count_2 ? count_1 : count_2;
        }
    }else{
        return 0;
    }
}

时间复杂度分析

完整源代码

#include <iostream>
#include <string>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <stdlib.h>
using namespace std;
 
 
const int X = 20, Y = 30;
 
//1.穷举法：递归实现
int LCS(string x, string y, char* result, int xlen, int ylen, int relen, int i, int j){
    if(i < xlen && j < ylen){
        if(x[i] == y[j]){
            result[relen] = x[i];
            relen++;
            return 1 + LCS(x, y, result, xlen, ylen, relen, i+1, j+1);
        }else{
            int count_1 = LCS(x, y, result, xlen, ylen, relen, i, j + 1);
            int count_2 = LCS(x, y, result, xlen, ylen, relen, i + 1, j);
            return count_1 > count_2 ? count_1 : count_2;
        }
    }else{
        return 0;
    }
}
 
int LCS_2(string x, string y, char* result, int xlen, int ylen, int relen, int i, int j){
    if(i >= 0 && j >= 0 && i < xlen && j < ylen){
        if(x[i] == y[j]){
            result[relen] = x[i];
            relen++;
            return 1 + LCS_2(x, y, result, xlen, ylen, relen, i - 1, j - 1);
        }else{
            int count_1 = LCS_2(x, y, result, xlen, ylen, relen, i, j - 1);
            int count_2 = LCS_2(x, y, result, xlen, ylen, relen, i - 1, j);
            return count_1 > count_2 ? count_1 : count_2;
 
        }
    }
    return 0;
}
 
//2.动态规划算法：递归实现（记忆化搜索）
int LCS_length_1(string x, string y, int tmp_1[][Y+1], int tmp_2[][Y+1], int xlen, int ylen, int i, int j){
    if(i >= 0 && j >= 0 && i <= xlen && j <= ylen){
        if(i == 0 || j == 0 || tmp_1[i][j] > 0){
            return tmp_1[i][j];
        }else{
            if(x[i-1] == y[j-1]){
                tmp_2[i][j] = 0;
                return tmp_1[i][j] = 1 + LCS_length_1(x, y, tmp_1, tmp_2, xlen, ylen, i-1, j-1);
            }else if((tmp_1[i][j-1] = LCS_length_1(x, y, tmp_1, tmp_2, xlen, ylen, i, j-1)) >=
                    (tmp_1[i-1][j] = LCS_length_1(x, y, tmp_1, tmp_2, xlen, ylen, i-1, j))){
                tmp_2[i][j] = 1;
                return tmp_1[i][j] = tmp_1[i][j-1];
            }else{
                tmp_2[i][j] = -1;
                return tmp_1[i][j] = tmp_1[i-1][j];
            }
        }
    }
 
    return 0;
}
 
//3.动态规划算法：非递归实现(递推实现，空间优化)
int LCS_length_2(string x, string y, int tmp_1[][Y+1], int tmp_2[][Y+1], int xlen, int ylen){
    int i = 0, j = 0, k = 0;
    //辅助数组的首行元素置为0
    for(i = 0; i <= xlen; i++){
        tmp_1[0][i] = 0;
    }
    tmp_1[1][0] = 0;
    //对数组内容进行写入
    for(i = 1; i <= xlen; i++){
        k = i%2;
        tmp_1[i%2][0] = 0;
        for(j = 1; j <= ylen; j++){
            if(x[i-1] == y[j-1]){
                tmp_1[k][j] = tmp_1[(i-1)%2][j-1] + 1;
                tmp_2[i][j] = 0;        //斜向下
            }else{
                if(tmp_1[k][j-1] >= tmp_1[(i-1)%2][j]){
                    tmp_1[k][j] = tmp_1[k][j-1];
                    tmp_2[i][j] = 1;        //向右
                }else{
                    tmp_1[k][j] = tmp_1[(i-1)%2][j];
                    tmp_2[i][j] = -1;       //向下
                }
            }
        }
    }
    return tmp_1[(i-1)%2][j-1];
}
 
 
//最大公共子序列输出函数，非递归实现
int LCS_print_1(string x, char *result, int tmp_2[][Y+1], int xlen, int ylen){
    int i = xlen, j = ylen, k = 0;
    while(i > 0 && j > 0 ){
        if(tmp_2[i][j] == 0){
            result[k] = x[i-1];         //斜向下
            k++;
            i--;
            j--;
        }else if(tmp_2[i][j] == 1){
            j--;                    //向右
        }else if(tmp_2[i][j] == -1){
            i--;                    //向下
        }
    }
    return k;
}
 
//-------------------------以下为测试代码----------------------------------------------------
 
//1.测试穷举法递归实现
void test_1(string x, string y){
    char result[X];
    int xlen = x.length();
    int ylen = y.length();
    //int max_len = LCS(x, y, result, xlen, ylen, 0, 0, 0);
    int max_len = LCS_2(x, y, result, xlen, ylen, 0, xlen - 1, ylen - 1);
    cout << "1.穷举法递归求最长公共子序列：" << endl;
    cout << "  最大公共子序列长度为：" << max_len << endl;
    /*
    for(int i = 0; i < max_len; i++){
        cout << result[i];
    }
    cout << endl;
    */
}
 
//2.测试动态规划算法递归实现
void test_2(string x, string y){
    //2.1参数处理
    char result[X+1];
    int xlen = x.length();
    int ylen = y.length();
    int tmp_1[X+1][Y+1] = {1};
    int tmp_2[X+1][Y+1] = {-2};
    //2.2初始化辅助数组
    memset(tmp_1,-1,sizeof(tmp_1));
    for(int i = 0; i <= xlen; i++){
        tmp_1[i][0] = 0;
    }
    for(int j = 0; j <= ylen; j++){
        tmp_1[0][j] = 0;
    }
    //2.3执行计算
    int max_len = LCS_length_1(x, y, tmp_1, tmp_2, xlen, ylen, xlen, ylen);
    LCS_print_1(x, result, tmp_2, xlen, ylen);
    //3.3打印结果
    cout << "2.动态规划法递归求最长公共子序列：" << endl;
    cout << "  最大公共子序列长度为：" << max_len << " 序列为：";
    for(int j = max_len - 1; j >= 0; j--){
        cout << result[j];
    }
    cout << endl;
}
 
//3.测试动态规划算法非递归实现
void test_3(string x, string y){
    //3.1参数处理
    char result[X+1];
    int xlen = x.length();
    int ylen = y.length();
    int tmp_1[2][Y+1] = {-2};
    int tmp_2[X+1][Y+1] = {-2};
    //3.2执行计算
    int max_len = LCS_length_2(x, y, tmp_1, tmp_2, xlen, ylen);
    LCS_print_1(x, result, tmp_2, xlen, ylen);
    //3.3输出结果
    cout << "3.动态规划法非递归求最长公共子序列：" << endl;
    cout << "  最大公共子序列长度为：" << max_len << " 序列为：";
    for(int j = max_len - 1; j >= 0; j--){
        cout << result[j];
    }
    cout << endl;
}
 
char* rand_string(char* str, int len){
    int i = 0;
    srand((unsigned)time(NULL));
    for(i = 0; i < len; i++){
        str[i] = rand()%26 + 'a';
    }
    str[i] = '\0';
    return str;
}
 
long getCurrentTime(){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}
 
int main()
{
    char str_1[X+1];
    rand_string(str_1,X);
    string x(str_1);
 
    sleep(1);
 
    char str_2[Y+1];
    rand_string(str_2,Y);
    string y(str_2);
 
    cout << "string x = " << x << endl;
    cout << "  字符串长度为：" << x.length() << endl;
    cout << "string y = " << y << endl;
    cout << "  字符串长度为：" << y.length() << endl;
 
    long time_1 = getCurrentTime();
    //test_1(x, y);
    long time_2 = getCurrentTime();
    cout << "  用时：";
    cout << time_2 - time_1 << " ms;" << endl;
 
    long time_3 = getCurrentTime();
    test_2(x, y);
    long time_4 = getCurrentTime();
    cout << "  用时：";
    cout << time_4 - time_3 << " ms;" << endl;
 
    long time_5 = getCurrentTime();
    test_3(x, y);
    long time_6 = getCurrentTime();
    cout << "  用时：";
    cout << time_6 - time_5 << " ms;" << endl;
 
    return 1;
}