最长公共子串和lcs

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

前言

感觉我对算法这一块的总结比较少，leetcode做题后没太注意总结各种算法，有时候会出现一道题目感觉就是会做但是思路总是会出一点问题。之后还是需要多做总结才行。

今天第一个需要注意的是 memset这个库函数。 这个函数可以用来对一块连续的空间做初始化。但是有一点我已知没有注意。这个函数的特性是分别对每一个字节进行初始化，也就是说对于一个64位机中的int类型进行初始化时，0x00000000初始化为1的结果是0x01010101。这一点还是挺重要的。之前都没有注意到。 类似的char（一个字节）的初始化就不用担心出错了。下面回到正题。

最长公共子串

给定两个字符串，找出他们的最长公共子串。”abcde”和”bcdf”返回”bcd”,这个题目可以联想到lcs，所以我顺便复习下lcs（最长公共子序列）。只要对lcs还有一点残存的记忆，想法都是使用二维数组来解题。
下面是关于”abcde”和”bcdf”的情况。

  b c d f     
a 0 0 0 0
b 1 0 0 0
c 0 1 0 0
d 0 0 1 0
e 0 0 0 0

观察上面的结构，最长子序列会出现在斜线上，这是一个典型的动态规划，他的递推式为

s1[i]==s2[j]? dp[i][j]=dp[i-1][j-1]+1;
最后结果就如下：

    b c d f     
  a 0 0 0 0
  b 1 0 0 0
  c 0 2 0 0
  d 0 0 3 0
  e 0 0 0 0

时间复杂度o(n2)，空间复杂度o(n2);

代码

代码如下：也可以输出其中的子串，方法比较多substr，或者遍历一下原串都可以。

#include<iostream>
#include<string>
#include<string.h>

using namespace std;

int getlen(string&s1,string &s2){
    int size1 = s1.size();
    int size2 = s2.size();
    int dp[size1][size2];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < size1;i++)
        dp[0][i] = s2[i] == s1[0] ? 1 : 0;

    for (int i = 0; i < size2;i++)
        dp[i][0] = s2[0] == s1[i] ? 1 : 0;


    int ret = 0;
    int indexx = 0;
    for (int m = 1; m < size1;m++){
        for (int n = 1; n < size2;n++){
            if(s1[m]==s2[n]){
                dp[m][n] = dp[m - 1][n - 1] + 1;
                if(dp[m][n]>ret){
                    ret = dp[m][n];
                    indexx = m;
                }
            }

        }
    }
    for (int i = 0; i < size1;i++){
        for (int j = 0; j < size2;j++)
            cout << dp[i][j] << " ";
         cout << endl;
    }


    string tmp = "";
    for (int i = indexx,j=ret; j>0&&i>=0;i--,j--){
        tmp =s1[i]+tmp;
    }
    cout << tmp << endl;
    return ret;
}

int main(){
    string s1,s2;
    cin>>s1>>s2;
    int len=getlen(s1,s2);
    cout<<len<<endl;
    return 0;
}

lcs

给定两个字符串，找出其中最长的公共子序列，注意子序列可以不是连续的字符，但是相对顺序不能变。
lcs是动态规划的典型，有很多类似的模型。比如地图最短路径，最大/最小正方形等。

这类问题的关键都是找到通项公式：lcs的通项如下：

lcs

所以一切的关键都在这个递归公式中，照着这个公式写就完全ok。有一篇文章图文并茂的博客总结的很好，感谢原作者.参考 https://blog.csdn.net/hrn1216/article/details/51534607

参考代码

可以在得出长度后再次返回去求得子串的组成元素。其中已经给出。

#include<iostream>
#include<string>
#include<string.h>
using namespace std;

int getlen(string& s1,string&s2){
    int len1 = s1.size();
    int len2 = s2.size();

    int dp[len1+1][len2+1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < len1;i++){
        for (int j = 0; j < len2;j++){
            if(s1[i]==s2[j]){
                dp[i + 1][j + 1] = dp[i][j]+1;
            }else{
                dp[i + 1][j + 1] = std::max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }

    for (int i = 0; i <= len1;i++){
        for (int j = 0; j <= len2;j++)
            cout << dp[i][j] << " ";
        cout << endl;
    }
    int m = len1, n = len2;
    string tmp = "";
    while(m>0 &&n>0 && dp[m][n]!=0){
        if(dp[m-1][n]==dp[m][n]){
            m = m - 1;
        }else if(dp[m][n-1]==dp[m][n]){
            n = n - 1;
        }else{
            m = m - 1;
            n = n - 1;
            tmp = s1[m] + tmp;
        }
    }

    cout << tmp << endl;
    return dp[len1][len2];
}

int main(){
    string s1, s2;
    cin >> s1 >> s2;

    int len = getlen(s1, s2);
    cout << len << endl;
    return 0;
}

以上代码都在牛客网对应题目中提交通过.