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