动态规划---求最长公共子序列和最长公共子串（C语言）

阳光穿透心脏的1/2处 2022-02-20 07:08 368阅读 0赞

参考：[https://blog.csdn.net/someone\_and\_anyone/article/details/81044153][https_blog.csdn.net_someone_and_anyone_article_details_81044153]

**一、求最长公共子序列**

1、问题描述：

从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）

要求：给定两个序列 X=\{x1,x2,…,xm\} 和 Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。

输入：输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

输出：每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

样例输入：  
13456778  
357486782

样例输出：  
5

**1、暴力解法：**  
假设 m<n， 对于母串X，我们可以暴力找出2的m次方个子序列，然后依次在母串Y中匹配，算法的时间复杂度会达到指数级O(n∗2的m次)。显然，暴力求解不太适用于此类问题。

**2、递归求解：**  
当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。  
在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。

**3、动态规划：**  
（1）创建DP数组C\[ \] \[ \]  
![在插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]  
（2）把首行和首列置零  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 1]  
（3）按照以下规则把表填满  
![在这里插入图片描述][20190412195659508.jpg]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 2]  
C\[8\]\[9\]=5即为所要求的最长公共子序列的长度

代码如下：

#include<stdio.h>
    #include<string.h>
    
    int max(int a,int b)
    { 
       return a>b?a:b;
    }
    int main()
    { 
        int i,j,k;
        char a[600];
        char b[600];
        int f[600][600];
        while(scanf("%s %s",a,b)!=EOF)
        { 
            int n=strlen(a);
            int m=strlen(b);
            for(i=0;i<=n;i++)
            { 
                f[i][0]=0;
            }
            for(i=0;i<=m;i++)
            { 
                f[0][i]=0;
            }
            for(i=1;i<=n;i++)
            { 
                for(j=1;j<=m;j++)
                { 
                    if(a[i-1]==b[j-1])
                    { 
                        f[i][j]=f[i-1][j-1]+1;
                    }
                    else
                    { 
                        f[i][j]=max(f[i-1][j],f[i][j-1]);
                    }
                }
            }
            printf("%d\n",f[n][m]);
        }
        return 0;
    }

S1和S2的最LCS并不是只有1个，本文并不是着重讲输出两个序列的所有LCS，只是介绍如何通过上表，输出其中一个LCS。  
我们根据递归公式构建了上表，我们将从最后一个元素c\[8\]\[9\]倒推出S1和S2的LCS。  
c\[8\]\[9\] = 5，且S1\[8\] != S2\[9\]，所以倒推回去，c\[8\]\[9\]的值来源于c\[8\]\[8\]的值(因为c\[8\]\[8\] > c\[7\]\[9\])。  
c\[8\]\[8\] = 5, 且S1\[8\] = S2\[8\], 所以倒推回去，c\[8\]\[8\]的值来源于 c\[7\]\[7\]。  
以此类推，如果遇到S1\[i\] != S2\[j\] ，且c\[i-1\]\[j\] = c\[i\]\[j-1\] 这种存在分支的情况，这里请都选择一个方向（之后遇到这样的情况，也选择相同的方向）

## 第一种结果为： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 3]  
这就是倒推回去的路径，棕色方格为相等元素，即LCS = \{3,4,6,7,8\}，这是其中一个结果。

如果如果遇到S1\[i\] != S2\[j\] ，且c\[i-1\]\[j\] = c\[i\]\[j-1\] 这种存在分支的情况，选择另一个方向，会得到另一个结果。  
![在这里插入图片描述][Center]  
即LCS =\{3,5,7,7,8\}。

**二、DP求解最长公共子串**

前面提到了子串是一种特殊的子序列，因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要，糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性，将二维数组c\[i\]\[j\]用来记录具有这样特点的子串——结尾同时也为为串x1x2⋯xi与y1y2⋯yj的结尾——的长度。  
得到转移方程：  
![在这里插入图片描述][20161116111138893]  
最长公共子串的长度为 max(c\[i,j\]), i∈\{1,⋯,m\},j∈\{1,⋯,n\}。

[https_blog.csdn.net_someone_and_anyone_article_details_81044153]: https://blog.csdn.net/someone_and_anyone/article/details/81044153
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70]: /images/20220220/f2a500f79028494a9c5b6dc2d4d958df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 1]: /images/20220220/51d857fca17c480088ef08d020b35f8e.png
[20190412195659508.jpg]: /images/20220220/15b80e76f3c049e2a00dfc19d7c53595.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 2]: /images/20220220/29d29fa9b7a6497da18323f17753594f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MDE2_size_16_color_FFFFFF_t_70 3]: /images/20220220/43c3d68596574a209b1eea24681db3d9.png
[Center]: /images/20220220/105d5a4dac2e4be2b49286c2f6441600.png
[20161116111138893]: /images/20220220/289582ff3c0f4e41ba148390914a1361.png