Longest Common Subsequence

  • The difference between the longest common substring and the longest common substring: the longest common substring is required to be continuous, the common subsequence is not required, but the order must be correct. For example, the longest common subsequence of abcDE and abefd is ab, and the longest common subsequence is abd. None of them are necessarily unique, but the length is unique.
  • Core ideas:
    • If the last element of both sequences is the same, then the last element of the LCS must be this; If the last element of two sequences is different, then the last element of the LCS may be either or neither, so the last element of one of the sequences is optional. For example, the “hello” and “heroine” LCS will be exactly the same as the “Hello” and “heroines” LCS. But there was no way to know which was useless.
    • So the LCS for “hello” and “hero” can be resolved to –> LCS for “hell” and “her” + ‘O’. The LCS of “hell” and “her” can then be resolved to the LCS of “hel” and “her” and “hell” and “he”, which are ultimately long sequences.
  • Implementation method:
    1. The sequence starts empty and increments, solving from the bottom up
      • You have to figure out the length of the oldest sequence, and then you derive the sequence
      • You can write code to figure out the length of the LCS just by understanding the following recursive formula or table
      • And if you understand the backward derivation of the LCS, you can write code to figure out the LCS
    2. Recursively, solving from the top down. Fill in later)

Recursive formula for length of LCS

LCS length two dimensional table

Line by line, principle: recursive formula for length of LCS

Retracing the LCS

code

#include <bits/stdc++.h>
using namespace std;

int main(a)
{
    string a, b, lcs;
    cin >> a;
    cin >> b;
    int len_a = a.length(a);int len_b = b.length(a);int dp[len_a + 1][len_b + 1];
    memset(dp, 0.sizeof(dp));

    / / length
    for (int i = 0; i < len_a; i++)
    {
        for (int j = 0; j < len_b; j++)
        {
            if (a[i] == b[j])
            {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            else if (dp[i][j + 1] > dp[i + 1][j])
                dp[i + 1][j + 1] = dp[i][j + 1];
            else
                dp[i + 1][j + 1] = dp[i + 1][j];
        }
    }

    cout << "the length of LCS is " << dp[len_a][len_b] << endl;

    / / the LCS
    for (int i = len_a - 1, j = len_b - 1; i >= 0;)
    {
        if (a[i] == b[j])
        {
            lcs = a[i] + lcs;
            i--;
            j--;
        }
        else if (dp[i][j + 1] > dp[i + 1][j])
            i--;
        else
            j--;
    }

    cout << "LCS = " << lcs << endl;
}
Copy the code

Do not know whether to speak clearly 😅, welcome to exchange correction! 😊