LCS算法及其时空优化

2023-10-09 15:10:10

经典算法

求解$LCS$（最长公共子序列）时，一般采用动态规划的方法。

例：有$strn$与$strm$两个序列，设$DP$方程$f[i][j]$表示$strn$的前$i$位与$strm$的前$j$位的LCS长度，转移方程如下:$$strn[i]==strm[j]:f[i][j]=f[i-1][j-1] +1$$

\[strn[i]!=strm[j]:f[i][j]=max(f[i][j-1],f[i-1][j]) \]

注意：上述两者可以相互独立，即当两字符相等的时候只进行第一步即可。

证明：$f[i-1][j-1]+1>=max(f[i][j-1],f[i-1][j])$必定成立。

时间复杂度：$O(nm)$
空间复杂度：$O(nm)$

for( int i = 0; i < len_n; i++ )
{
    for( int j = 0; j < len_m; j++)
    {
        if(strn[i] == strm[j])
        {
            f[i][j] = f[i-1][j-1] + 1; 
        }
        else 
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
}

空间复杂度优化

注意到转移时只与$f[i-1][j-1]、f[i-1][j]、f[i][j-1]$有关，因此可以尝试滚动数组优化。

设$dp[j]$代表当前循环到$strn$的第$i$个字符时的答案构成的数组。
在更新$dp[j]$时，即是对应经典算法中的$dp[i][j]$，则此时$dp[j]$中保留的数据应该是$dp[i-1][j]$，而$dp[j-1]$保留的数据是$dp[i][j-1]$。
那么应该如何获得$dp[i-1][j-1]$呢？
可以开一个临时变量$temp$，保留每一次更新前的$dp[j]$（相当于$dp[i-1][j]$），则当循环进行到第$j+1$个字符时，$temp$内保留的数据就相当于我们要求的$dp[i][j]$，故问题得到了解决。

代码如下：

for (i = 0; i < len_n; i++)
{
    temp = 0;
    for (j = 0; j < len_m; j++)
    {
        now_val = dp[j];//now_val代表dp[i-1][j]的值
        if (strn[i] == strm[j])
            dp[j] = temp + 1;//代表dp[i-1][j-1]+1
        else
            dp[j] = max(dp[j - 1], dp[j]);//dp[j-1]代表dp[i][j-1]
        temp = now_val;//保留dp[i-1][j]的值
    }
}

空间复杂度：$O(n)$

时间复杂度优化

适用条件：序列中重复元素较少，最好为排列

思路：考虑每一个出现在$strn$的字符，在$strm$中找到其出现的所有位置并加以分类降序储存在数组中。再把每一个字符对应的坐标按照对应字符在$strn$中出现的下标**顺序排列成一个新序列$M$，则$M$的LIS（最长上升子序列）即是所求答案。

例：

strn=abscsa
strm=adbsccab

则
a在strm的坐标为0、6
b在strm的坐标为2、7
s在strm的坐标为3
c在strm的坐标为4、5

则序列M为

6 0 7 2 3 5 4 3 6 0

LIS长度为5
故LCS长度为5

$tips:$

正确性：求出$M$的最长上升子序列保证了这些字符在$strm$中升序出现，又因为这些字符是按照在$strn$中的坐标升序排列的，故为两者的$LCS$。
选择降序排列坐标数组：防止同一个位置的字符被多次选取计算。
如何在$O(n)$时间内得到坐标数组：使用链表或者动态数组

void solve(char *str1, char *str2)
{
    len_n = strlen(str1), len_m = strlen(str2);
    for(int i = 0; i < len_n; i++)
    {
        inv[str1[i] - ' '] = true;
        head[str1[i] - ' '] = -1;
    }
    for(int i = 0; i < len_m; i++)
    {
        if(inv[str2[i] - ' ']) 
        {   
            next[i] = head[str2[i] - ' '];
            head[str2[i] - ' '] = i;   
        }
    }
    for(int i = 0; i < len_n; i++)
    {
        int now_pos = head[str1[i] - ' '];
        while (now_pos != -1)
        {
            str[str_len++] = now_pos;//同时实现了降序排序的要求
            now_pos = next[now_pos];
        }
    }
}

上述代码实现了构造序列$M$（即是代码中的$str$）的任务。

时间复杂度：对于没有重复元素的序列，时间复杂度为$O(n)$，随序列中元素重复度升高而升高，最坏可以为$O(n^2)$，即整个序列只有一种元素。

求解$LIS$可以使用树状数组优化，时间复杂度为$O(nlogn)$

因此总复杂度较好情况下为$O(nlogn)$。

码农公寓

经典算法

空间复杂度优化

时间复杂度优化

适用条件：序列中重复元素较少，最好为排列

相关文章