最长公共子串、最长公共子序列、字符串编辑距离

最长公共子串、最长公共子序列、字符串编辑距离

 

最长公共子串

 

问题描述

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

基本方法

大凡基本方法都是枚举方法，这里其实就枚举所有长度相等的子串进行比较。枚举方法时没有考虑一切实际情况的，这样就有很多“漏洞”，就可以有很多优化的方法。

 

动态规划

╔

使用dp[i][j]表示 以x[i]和y[j]结尾的最长公共子串的长度，因为要求子串连续，所以对于X[i]与Y[j]来讲，它们要么与之前的公共子串构成新的公共子串；要么就是不构成公共子串。故状态转移方程 X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1 X[i] != Y[j]，dp[i][j] = 0 对于初始化，i==0或者j==0，如果X[i] == Y[j]，dp[i][j] = 1；否则dp[i][j] = 0。这样的处理跟连续子数组最大和有点类似，只是连续子数组子和是当dp[i]<0时执行dp[i]=0。

 

/* 最长公共子串 DP */
int dp[30][30];
 
void LCS_dp(char * X, int xlen, char * Y, int ylen)
{
    maxlen = maxindex = 0;
    for(int i = 0; i < xlen; ++i)
    {
        for(int j = 0; j < ylen; ++j)
        {
            if(X[i] == Y[j])
            {
                if(i && j)
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 1;
                }
                if(dp[i][j] > maxlen)
                {
                    maxlen = dp[i][j];
                    maxindex = i + 1 - maxlen;
                }
            }
        }
    }
    outputLCS(X);
}

 

后缀数组求解

后缀数组在前面的博文有介绍， 如果将两个字符串连接起来成新字符串，最长公共子串问题就转化为新字符串的最长重复子串的问题（点击前往）了，唯一的区别就是要区别来着同一个字符的最大重复子串。

这里就不在列举了，在处理过程中要对后缀数组进行排序操作，可以考虑重后缀子串的长度的影响——公共子串的长度一定是相等的。

时间复杂度分析

对于基本算法，X的子串（m个）和Y的子串（n个）一一对比，最坏情况下，复杂度为O(m*n*l)，空间复杂度为O(1)。

对于动态规划算法，由于自底向上构建最优子问题的解，时间复杂度为O(m*n)；空间复杂度为O(m*n)，当然这里是可以使用滚动数组来优化空间的，滚动数组在动态规划基础回顾中多次提到。 对于后缀数组方法，连接到一起并初始化后缀数组的时间复杂度为O(m+n)，

对后缀数组的字符串排序，由于后缀数组有m+n个后缀子串，子串间比较，故复杂度为O((m+n)*l*lg(m+n))，求得最长子串遍历后缀数组，复杂度为O(m+n)，所以总的时间复杂度为O((m+n)*l*lg(m+n))，空间复杂度为O(m+n)。 总的来说使用后缀数组对数据做一些“预处理”，在效率上还是能提升不少的。

╝①

 

最长公共子序列

 

问题描述

╔

最长公共子序列就是寻找两个给定序列的子序列，该子序列在两个序列中以相同的顺序出现，但是不必要是连续的。

动态规划求解

使用动态规划求解这个问题，先寻找最优子结构。设X=<x₁,x₂,…,x_m>和Y=<y₁,y₂,…,y_n>为两个序列，LCS(X,Y)表示X和Y的一个最长公共子序列，可以看出

1. 如果x_m=y_n，则LCS ( X,Y ) = x_m + LCS ( X_m-1,Y_n-1 )。
2. 如果x_m!=y_n，则LCS( X,Y )= max{ LCS ( X_m-1, Y ), LCS ( X, Y_n-1 ) }

LCS问题也具有重叠子问题性质：为找出X和Y的一个LCS，可能需要找X和Y_n-1的一个LCS以及X_m-1和Y的一个LCS。但这两个子问题都包含着找X_m-1和Y_n-1的一个LCS，等等。

为了找到最长的LCS，我们定义dp[i][j]记录序列LCS的长度，合法状态的初始值为当序列X的长度为0或Y的长度为0，公共子序列LCS长度为0，即dp[i][j]=0，所以用i和j分别表示序列X的长度和序列Y的长度，状态转移方程为 dp[i][j] = 0 如果i=0或j=0 dp[i][j] = dp[i-1][j-1] + 1 如果X[i-1] = Y[i-1] dp[i][j] = max{ dp[i-1][j], dp[i][j-1] } 如果X[i-1] != Y[i-1] 求出了最长公共子序列的长度后，输出LCS就是输出dp的最优方案了，既可以用一个额外的矩阵存储路径，也可以直接根据状态转移矩阵倒推最优方案。

 

#include <iostream>
using namespace std;
 
/* LCS
 * 设序列长度都不超过20
*/
 
int dp[21][21]; /* 存储LCS长度, 下标i,j表示序列X,Y长度 */
char X[21];
char Y[21];
int i, j;
 
void main()
{
    cin.getline(X,20);
    cin.getline(Y,20);
 
    int xlen = strlen(X);
    int ylen = strlen(Y);
 
    /* dp[0-xlen][0] & dp[0][0-ylen] 都已初始化0 */
    for(i = 1; i <= xlen; ++i)
    {
        for(j = 1; j <= ylen; ++j)
        {
            if(X[i-1] == Y[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }else if(dp[i][j-1] > dp[i-1][j])
            {
                dp[i][j] = dp[i][j-1];
            }else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    printf("len of LCS is: %d\n", dp[xlen][ylen]);
 
    /* 输出LCS 本来是逆序打印的，可以写一递归函数完成正序打印
       这里采用的方法是将Y作为临时存储LCS的数组，最后输出Y
    */
i = xlen;
j = ylen;
int k = dp[i][j];
char lcs[21] = {'\0'};
while(i && j)
{

    if(X[i-1] == Y[j-1] && dp[i][j] == dp[i-1][j-1] + 1)

    {

        lcs[--k] = X[i-1];

        --i; --j;

    }else if(X[i-1] != Y[j-1] && dp[i-1][j] > dp[i][j-1])

    {

        --i;

    }else

    {

        --j;

    }
}
printf("%s\n",lcs);

}

 

 

 

  在LCS问题中，如果仅仅要求求出LCS的长度，而不要求输出序列，那么由于每步迭代都只用到了前面的状态，之前的信息便无用了，就可以使用滚动数组了。

 

#include <iostream>
using namespace std;
 
/* 滚动数组 */
 
int dp[2][21];  /* 存储LCS长度 */
char X[21];
char Y[21];
int i, j, k;
 
void main()
{
    cin.getline(X,20);
    cin.getline(Y,20);
 
    int xlen = strlen(X);
    int ylen = strlen(Y);
 
    for(i = 1; i <= xlen; ++i)
    {
        k = i & 1;
        for(j = 1; j <= ylen; ++j)
        {
            if(X[i-1] == Y[j-1])
            {
                dp[k][j] = dp[k^1][j-1] + 1;
            }else if(dp[k][j-1] > dp[k^1][j])
            {
                dp[k][j] = dp[k][j-1];
            }else
            {
                dp[k][j] = dp[k^1][j];
            }
        }
    }
    printf("len of LCS is: %d\n", dp[k][ylen]);
}

╝②

 

字符串编辑距离

 

问题描述

╔

字符串编辑距离又叫字符串相似度，编辑距离就是将两个不同的字符串变成相同字符串所需要操作的次数的最小值。而这些操作只有以下三种：

1)修改一个字符

2)增加一个字符

3)删除一个字符

 

寻找子问题时，我们完全可以像分析最长公共子序列那样分析这个问题，都是“从后向前”看，假设有两个串X=abcdaex，Y=fdfax，它们的最后一个字符是相同的，只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了；但是如果两个串的最后一个字符不相同，那么就可以进行如下的操作来达到目的（xlen和ylen是X串和Y串的长度）：

 

1.一步操作之后，再计算X[1,…,xlen-1]和Y[1,…ylen]的距离。这个操作可以是删除X的最后一个字符，也可以是增加X串的最后一个字符到Y串的最后字符之后

2.一步操作之后，再计算X[1,…,xlen]和Y[1,…ylen-1]的距离。这个操作与情况1类似，反过来而已

3.一步操作之后，再计算X[1,…,xlen-1]和Y[1,…ylen-1]的距离。这个操作可以是修改X串的最后有一个字符为Y串的最后一个字符，后者修改Y的变为X的最后一个字符，使得二者相同。

 

 

dp[i][j]中的i和j表示串X和Y的长度，其中，如果某一个串的长度为0，则编辑距离就是另一个串的长度，这很容易理解。状态转移方程为

 

1.dp[i][j] = 0  如果i=0 & j=0

2.dp[i][j] = xlen | ylen  如果j=0 | i=0

3.dp[i][j] = dp[i-1][j-1]  如果X[i-1] = Y[i-1]

4.dp[i][j] = 1 + min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }  如果X[i-1] != Y[i-1]

 

下面给出了三种实现方式，第一种是根据分析给出的递归搜索方法；由于具有重叠子问题，所以第二种方法便是使用了备忘录的递归方法（注：分治与动态规划的重要区别就是分治递归不断产生新的子问题，没有重叠子问题；而DP则是在递归不断产生子问题的同时很多子问题是重复计算的，即重叠子问题）；第三种便是根据状态转移方程给出了自底向上的实现，这也是最符合DP性质的实现方式。

简单递归搜索

 

/* 递归搜索 */
int calDistance1(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend)
{
    if(xbeg > xend)
    {
        if(ybeg > yend)
            return 0;
        else
            return yend - ybeg + 1;
    }
    if(ybeg > yend)
    {
        if(xbeg > xend)
            return 0;
        else
            return xend - xbeg + 1;
    }
    if(ptrX[xend] == ptrY[yend])
    {
        return calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
    }else
    {
        int t1 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend);
        int t2 = calDistance1(ptrX,xbeg,xend,ptrY,ybeg,yend-1);
        int t3 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
        t1 = t1 < t2 ? t1 : t2;
        return (t1 < t3 ? t1 : t3) + 1;
    }
}

 

 递归+备忘录

 

/* 编辑距离
 * 设每个字符串长度不超过 30
*/
 
/* 存储子问题的解 i,j表示X，Y长度
 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离
*/
int dp[31][31];
/* 自顶向下 & 备忘录 */
int calDistance2(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend)
{
    if(xend == 0)
    {
        if(yend == 0)
            return 0;
        else
            return yend - ybeg + 1;
    }
    if(yend == 0)
    {
        if(xend == 0)
            return 0;
        else
            return xend - xbeg + 1;
    }
    if(ptrX[xend-1] == ptrY[yend-1])
    {
        if(dp[xend-1][yend-1] == 0)
        {
            dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
        }
        return dp[xend-1][yend-1];
    }else
    {
        int t1, t2, t3;
        if(dp[xend-1][yend] == 0)
        {
            dp[xend-1][yend] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend);
        }
        t1 = dp[xend-1][yend];
        if(dp[xend][yend-1] == 0)
        {
            dp[xend][yend-1] = calDistance2(ptrX,xbeg,xend,ptrY,ybeg,yend-1);
        }
        t2 = dp[xend][yend-1];
        if(dp[xend-1][yend-1] == 0)
        {
            dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
        }
        t3 = dp[xend-1][yend-1];
        t1 = t1 < t2 ? t1 : t2;
        return (t1 < t3 ? t1 : t3) + 1;
    }
}

 

自底向上动态规划

/* 编辑距离
 * 设每个字符串长度不超过 30
*/
 
/* 存储子问题的解 i,j表示X，Y长度
 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离
*/
int dp[31][31];
char X[31];
char Y[31];
/* 自底向上 DP */
int calDistance3(char *ptrX, int xlen, char *ptrY, int ylen)
{
    int i, j;
    for(i = 1; i <= xlen; ++i)
    {
        dp[i][0] = i;
    }
    for(j = 1; j <= ylen; ++j)
    {
        dp[0][j] = j;
    }
    for(i = 1; i <= xlen; ++i)
    {
        for(j = 1; j <= ylen; ++j)
        {
            if(ptrX[i-1] == ptrY[j-1])
            {
                dp[i][j] = dp[i-1][j-1];
            }else
            {
                int t1 = dp[i-1][j];
                t1 = t1 < dp[i][j-1] ? t1 :dp[i][j-1];
                t1 = t1 < dp[i-1][j-1] ? t1 : dp[i-1][j-1];
                dp[i][j] = t1 + 1;
            }
        }
    }
    return dp[xlen][ylen];
}

一并给出测试用例

#include <iostream>
using namespace std;
void main()
{
    cin.getline(X,30);
    cin.getline(Y,30);
 
    int xlen = strlen(X);
    int ylen = strlen(Y);
 
    printf("%d\n",calDistance1(X,0,xlen-1,Y,0,ylen-1));
    //printf("%d\n",calDistance2(X,0,xlen,Y,0,ylen));
    printf("%d\n",calDistance3(X,xlen,Y,ylen));
}

╝③   

 

 

参考：

①勇幸|Thinking： http://www.ahathinking.com/archives/122.html

②勇幸|Thinking： http://www.ahathinking.com/archives/115.html

③勇幸|Thinking： http://www.ahathinking.com/archives/116.html