Longest common subsequence and longest common substring problem

In 2019, dJI test development post only one programming problem is the longest common subsequence problem. After a look, there is also a common problem is the longest common subsequence problem. Today, I summarize it together.

Longest common subsequence

1. Niuke.com address [can be passed all]

Ctrl/Cmd + K www.nowcoder.com/practice/47…

Problem 2.

Given two strings str1 and str2, return the longest common subsequence of the two strings, for example: str1=”1A2C3D4B56″,str2=”B1D23CA45B6A”, “123456”, and “12C4B6” are the longest common subsequences. Input: 1A2C3D4B56 B1D23CA45B6A Output: 123456 Note: “123456” and “12C4B6” are the longest common subsequences, any output.

3. Code

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
 using namespace std;

#define M 10000
#define N 10000
int dp[M][N];

string findTheLongestSameStr(string str1, string str2, int len1, int len2)
{
    string result;
    if (len1 == 0 || len2 == 0)
        return result;
    int m = len1 + 1;
    int n = len2 + 1;

    / / initialization
    for (int i = 0; i < m; i++)
        dp[i][0] = 0;
    for (int j = 0; j < n; j++)
        dp[0][j] = 0;
    // Fill the matrix
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
        {
            if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    //cout << dp[m - 1][n - 1] << endl; // Outputs the longest common subsequence length

    // Find the longest common subsequence
    for (int i = m - 1, j = n - 1; (i > 0) && (j > 0); {if (str1[i - 1] == str2[j - 1])
        {
            result = str1[i - 1] + result;
            i--;
            j--;
        }
        else if (dp[i - 1][j] > dp[i][j - 1])
            i--;
        else
            j--;
    }
    return result;
}

int main(a)
{
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    int len1 = str1.size();
    int len2 = str2.size();
    string result = findTheLongestSameStr(str1, str2, len1, len2);
    cout << result << endl;
    return 0;
}
Copy the code

Longest common substring

1. Niuke.com address [only through part of the memory exceeded]

Ctrl/Cmd + K www.nowcoder.com/practice/21…

Problem 2.

Find the longest common substring length in two strings STR and str2. For example, if STR = ACBCBCEf, str2= abCBced, the longest common substring of STR and str2 is BCBCE, and the longest common substring length is 5

3. The train of thought

Preliminary:

(1) Construct matrix dp[I][J]

(2) if str1[I]==str2[j],dp[I][j]=1, otherwise 0

(3) The longest common substring can be found by looking for the longest diagonal value of 1

Ctrl/Cmd + Shift + I

Update:

(1) Set the dp scale as LEN1 and Len2

(2) if str1[I]==str2[j],dp[I][j]= DP [i-1][J-1]+1, otherwise 0

(3) the maximum value of dp[I][j] is the longest common subsequence length Max, and the longest common subsequence is str2. Substr (jmax-max, Max)

Ctrl/Cmd + Shift + I

Code 4.

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

#define M 100
#define N 100
int dp[M][N];

void findTheMaxSameStr(string str1, string str2)
{
       int len1 = str1.size();
       int len2 = str2.size();
       int m = len1 + 1;
       int n = len2 + 1;
       string result;
       if (len1 == 0 || len2 == 0)
       {
              cout << result <<endl;
              return;
       }
       
       // Populate the DP matrix
       int max=0, imax=0, jmax=0;
       for(int i=1; i<m ; i++)for (int j = 1; j < n; j++)
              {
                     if (str1[i - 1] == str2[j - 1])
                     {
                           dp[i][j] = dp[i - 1][j - 1] + 1;
                           if(dp[i][j] > max) { max = dp[i][j]; imax = i; jmax = j; }}}cout << max << endl;
       result = str2.substr(jmax-max, max);
       cout << result << endl;
       return;
}

int main(a)
{
       string str1, str2;
       getline(cin, str1);
       getline(cin, str2);
       memset(dp, 0.sizeof(dp));
       findTheMaxSameStr(str1, str2);
       return 0;
}
Copy the code

Longest common subsequence and longest common substring problem