DP longest common subsequence detailed version (LCS)

Longest common subsequence , This is a B standing A blogger's explanation video , It's very good. , After watching this video, you can even stop reading my blog , But if you think the video is too long , Welcome to continue to see the essence content extracted from the video .

Catalog

1、 Definition

2、 Regular questions

3、 Their thinking

 4、 Solution code

5、 Expand

---

1、 Definition

Longest common subsequence （LCS） It's one in a sequence set （ It's usually two sequences ） The problem of finding the longest subsequence in all sequences . A sequence of  , If they are subsequences of two or more known sequences , And is the longest of all sequences that meet this condition , Is called the longest common subsequence of a known sequence .
The above explanation is given by Baidu , Let me explain it in vernacular , In fact, it means giving several different strings （ It's usually two ）, Then find their common subsequence , It can be discontinuous . for instance , character string algorithms and alchemist（ To facilitate observation ,LCS I use bold red to indicate ） Of LCS namely alhms.

2、 Regular questions

describe ：

Given two sequences s1、s2, Find the length of the common subsequence of two rules .

Input ：

On the first line, enter the first sequence

On the second line, enter the second sequence

Output ：

Output a number , That is, the length of the common subsequence of two sequences .

3、 Their thinking

Dynamic programming is mainly used , But make clear the meaning .

① Design status

set up f[i][j] It's a sequence si={x1,x2,...,xi} And sequence sj={y1,y2,...,yj}  The length of the common subsequence of .

② State transition equation

Now? i、j Corresponding to three different equations

f[i][j] = 0  -->  i=0 perhaps j=0,si and sj The length of any sequence in is zero , So their LCS The length can only be zero

f[i][j] = f[i-1][j-1] + 1 --> xi=yj, The last characters of the two sequences are equal , Explain that the length should be increased by at least one , Add one and cut this character directly , Then continue to compare i-1 and j-1 Corresponding characters , Compare in turn

f[i][j] =max（f[i-1][j],f[i][j-1]）--> xi！=yj, This is illustrated by an example , Suppose to ask for abcd and acde Of LCS length , character d！=e, Now there are two options , Either ask abcd and acd Of LCS, Either ask abc and acde Of LCS, But since it is the longest LCS, Then choose the maximum value of the two schemes .

 4、 Solution code

//  Find the longest common subsequence  -- dp 
#include <bits/stdc++.h>
using namespace std;
char s1[100],s2[100];
int f[100][100];
int main()
{
	int n,m,i,j;
	gets(s1);
	gets(s2);
	n=strlen(s1),m=strlen(s2);
	//  State transition equation one  --> f[100][100] It was all zero , Never mind  
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(s1[i-1]==s2[j-1])  f[i][j]=f[i-1][j-1]+1;  //  Fang Chenger 
			else   f[i][j]=max(f[i-1][j],f[i][j-1]);   //  Equation 3  
		}
	} 
	cout<<f[n][m]; 
	return 0;
}
/* Case study  
algorithms
alchemist
 result ： 5 
*/ 

 

5、 Expand

What the above code solves is LCS The length of , Now let's try to find this sequence directly , Not the length .

//  Find the longest common subsequence  -- dp 
#include <bits/stdc++.h>
using namespace std;
char s1[100],s2[100];
int f[100][100];
void LCS(int i,int j)
{
	if(i==0||j==0)  return ;  // to flash back  
	if(s1[i-1]==s2[j-1])
	{
		LCS(i-1,j-1);  // recursive 
		cout<<s1[i-1]; 
	}
	else if(f[i-1][j]>f[i][j-1])
	{
		LCS(i-1,j);
	}
	else
	{
		LCS(i,j-1);
	} 
} 
int main()
{
	int n,m,i,j;
	gets(s1);
	gets(s2);
	n=strlen(s1),m=strlen(s2);
	//  State transition equation one  --> f[100][100] It was all zero , Never mind  
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(s1[i-1]==s2[j-1])  f[i][j]=f[i-1][j-1]+1;  //  Fang Chenger 
			else   f[i][j]=max(f[i-1][j],f[i][j-1]);   //  Equation 3  
		}
	} 
	cout<<f[n][m]<<endl;    //  Sequence length  
	LCS(n,m);  //   Find sequence    function  
	return 0;
}
/* Case study  
algorithms
alchemist
 result ： 
5 
alhms
*/ 

result :