This is the 21st day of my participation in the August More Text Challenge

preface

Today comes a topic of the longest common subsequence problem, which was touched on a long time ago. Today, I share it with the friends of the nuggets. Without saying much, I go directly to the topic

Topic describes

Given two strings A and B, find the longest common subsequence of A and B (not contiguous subsequence). For example, two strings are:

abcicba abdkscab

Ab is a subsequence of two strings, as is ABC, and as is abca, where ABCA is the longest subsequence of the two strings. The input

Line 1: string A Line 2: string B (length of A,B <= 1000)

The output

Print the longest subsequence, if there are more than one, print 1 at will.

The input sample

abcicba

abdkscab

Sample output

abca

Solving process: a two-dimensional array C [][] is introduced, c[I][j] is used to record the length of LCS of X[I] and Y[j], and B [I][j] is used to record the value of which subproblem C [I][j] is obtained to determine the direction of search. We perform bottom-up recursive calculation, so c[i-1][J-1], C [i-1][j] and C [I][J-1] have been calculated before c[I,j] is calculated. If X[I] = Y[j] or X[I]! = Y[j], we can calculate c[I][j].

The recursive expression is:

The procedure for backtracking the longest common subsequence:

Algorithm analysis

Since each call moves at least one step up or left (or both), at most (m + n) calls, I = 0 or j = 0 is encountered, at which point the return begins. The return direction is opposite to the recursive call and the number of steps is the same, so the algorithm time complexity is O (m + N).

The following code

#include<iostream>
#include<iomanip>
#include <string.h>
using namespace std;
long int c[1001] [1001];
int main(a)
{
    string a,b;
    char d[1000];
    long long int n1,n2,i,j,k;
    cin>>a>>b;
    //n1=strlen(a); Strlen (for arrays)
    //n2=strlen(b);
    n1=a.size(a); n2=b.size(a); k=0;
    for(i=1; i<=1000; i++){c[0][i]=0; c[i][0] =0; }for(i=1; i<=n1; i++)for(j=1; j<=n2; j++) c[i][j]=(a[i- 1]==b[j- 1])? (c[i- 1][j- 1] +1) :max(c[i][j- 1],c[i- 1][j]);
             for(i=n1,j=n2; i>=1&&j>=1;)
                {
                    if(a[i- 1]==b[j- 1])
                    {
                        d[k]=a[i- 1];
                        k++;
                        i--;
                        j--; 
                    }
                    else
                    {
                        if(c[i][j- 1]>c[i- 1][j])// Can also be equal to, it doesn't matter, equal to would change the backtrace
                        {
                            j--;
                        }
                        else{ i--; }}}for(i=k- 1; i>=0; i--)cout<<d[i]; cout<<endl;return 0;
}
Copy the code

conclusion

Today, this problem is a little difficult, although it is done before and also recalled for a long time, the core of this problem is to find the recursive expression, and then easy to do, share with everyone, gogogo