This is the 18th day of my participation in the August Challenge

Definition:

Let sequence M be A subsequence of sequence A (length n) and sequence B(length M), and the longest subsequence of all subsequences conforming to both sequences A and B, then sequence M is the oldest sequence we seek to solve.

Application:

Compare the similarities between the two articles.

methods

Method one, enumeration method

A has 2N subsequences (there are only two choices of n numbers: take or not take), and determine whether each subsequence is the longest subsequence with time complexity O(m2n).

Method 2. Dynamic programming DP

Let L[I,j] represent the longest common subsequence length of Ai and Bj, then

Design an array of strings to hold the longest common subsequence. Two arrays of integers to hold the subsequence of the longest common subsequence in strings A and B.

(1) C++ defines a two-dimensional array

    // Request space
    int** a2 = new int*[rows];
    for(int i=0; i<rows; i++) a2[i] =new int[columns];
    // Free up space
    for(int i=0; i<rows; i++)delete []a2[i];
    delete []a2;
Copy the code
#include<iostream>
#include<string>
#include<stack>
using namespace std;
// Generate a two-dimensional array with m rows and n columns
void LCS(string s1,string s2)
{
    int m=s1.length() +1;
    int n=s2.length() +1;
    int **c;
    int **b;
    c=new int* [m];
    b=new int* [m];
    for(int i=0; i<m; i++){ c[i]=new int[n];
        b[i]=new int[n];
        for(int j=0; j<n; j++) b[i][j]=0; 
    }
    // The longest string is 0 regardless of whether the first string or the second string is 0
    for(int i=0; i<m; i++) c[i][0] =0;
    for(int i=0; i<n; i++) c[0][i]=0;
    for(int i=0; i<m- 1; i++) {for(int j=0; j<n- 1; j++) {if(s1[i]==s2[j])
            {
                c[i+1][j+1]=c[i][j]+1;
                b[i+1][j+1] =1;// Use 1 to indicate the arrow
            }
            else if(c[i][j+1]>=c[i+1][j])
            {
                c[i+1][j+1]=c[i][j+1];
                b[i+1][j+1] =2;//2 indicates arrow ↑
            }
            else
            {
                c[i+1][j+1]=c[i+1][j];
                b[i+1][j+1] =3;//3 indicates arrow ←}}}for(int i=0; i<m; i++) {for(int j=0; j<n; j++) { cout<<c[i][j]<<' ';
        }
        cout<<endl;
    }

    stack<char> same;// Store the longest common subsequence
    stack<int> same1,same2; // Store the subscript of the longest common subsequence in string 1 and string 2 for easy display
    for(int i=m- 1,j=n- 1; i>=0&&j>=0;)
    {
        if(b[i][j]==1)
        {
            i--;
            j--;
            same.push(s1[i]);/ / or s2 [j].
            same1.push(i);
            same2.push(j);
        }
        else if(b[i][j]==2)
            i--;
        else
        {
            j--;
        }
    }
        cout<<s1<<endl;/ / output s1
        for(int i=0; i<m && ! same1.empty(a); i++)// Prints the token of string 1
        {
            if(i==same1.top())
            {
                cout<<1;
                same1.pop(a); }else
            {
                cout<<' ';
            }
        }
        cout<<endl<<s2<<endl;
        for(int i=0; i<n && ! same2.empty(a); i++) {if(i==same2.top())
            {
                cout<<1;
                same2.pop(a); }else
            {
                cout<<' ';
            } 
        }
           cout<<endl<<"The longest common subsequence is:";
    while(! same.empty())
    {
        cout<<same.top(a); same.pop(a); } cout<<endl<<"Length:"<<c[m- 1][n- 1]<<endl;
    for (int i = 0; i<m; i++)
    {
        delete [] c[i];
        delete [] b[i];
    }
    delete []c;
    delete []b;
}
int main(a)
{
    string s1="ABCPDSFJGODIHJOFDIUSHGD";
    string s2="OSDIHGKODGHBLKSJBHKAGHI";
    LCS(s1,s2);
    system("pause");
    return 0;
}
Copy the code