最长公共子序列,最长公共连续子序列及动态规划问题

对于最长连续子序列，见下题

题目描述

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

输入描述:

输入两个字符串

输出描述:

返回重复出现的字符

示例1

输入

复制

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

复制

jklmnop

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    string a, b;
    while (cin >> a >> b)
    {
        if(a.size()>b.size())
            swap(a,b);
        int len1=a.size(),len2=b.size();
        int max_length=0;
        int start_pos=0;
        vector<vector<int>> vec_vec_int(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(a[i-1]==b[j-1])
                {
                    vec_vec_int[i][j]=vec_vec_int[i-1][j-1]+1;
                    if(vec_vec_int[i][j]>max_length)
                    {
                        max_length=vec_vec_int[i][j];
                        start_pos=i-max_length;
                    }
                    
                }
            }
        }
        cout<<a.substr(start_pos,max_length)<<endl;
    }
    return 0;
}

对于最长子序列，不要求连续

题目:

Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not).
A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.

Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3    Explanation: The longest common subsequence is “ace” and its length is 3.

Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3    Explanation: The longest common subsequence is “abc” and its length is 3.

Example 3:
Input: text1 = “abc”, text2 = “def”
Output: 0    Explanation: There is no such common subsequence, so the result is 0.

解:

 LCS 重点就是想明白递推公式：

if text1[i] == text2[j]，那么 lcs[i + 1][j + 1] = lcs[i][j] + 1
else，lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j])（与上面的区别，连续的不相等的就不需要保存）
  这种二维矩阵 DP 问题，一般 DP 矩阵都会比数据多一个大小的位置，这样方便初始化，如下图，将所有初始化为0：

int longestCommonSubsequence(string text1, string text2) {
    const int len1 = text1.length(), len2 = text2.length();
    vector<vector<int>> lcs(len1 + 1, vector<int>(len2 + 1, 0));　　//二维数组的题，大部分要多申请一个空间
    for(int i=0;i<len1;i++)
　　{
　　　　for(int j=0;j<len2;i++)
　　　　{
　　　　　　if(text1[i]==text2[j])
　　　　　　{
　　　　　　　　lcs[i+1][j+1]=lcs[i][j]+1;
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　lsc[i+1][j+1]=max(lsc[i][j+1],lsc[i+1][j]);
　　　　　　}
　　　　}
　　　　//如果要获取字符串值，根据lsc中的下标获取text1或者text2的字符即可
　　}
　　return lcs[len1][len2];
}

参考

https://blog.csdn.net/Bob__yuan/article/details/99690889

另附两个地址

https://www.cnblogs.com/wkfvawl/p/9362287.html

https://blog.csdn.net/trochiluses/article/details/37966729