Longest common subsequence

The problem of the Longest Common SubSequence is described as follows:

Given two strings A and B, find A string that is the longest common part of A and B

For example, the longest common subsequence of “sadstory” and “adminsorry” is “adsory” and is 6 in length

If it’s a violent traversal… Let the lengths of A and B be n and m respectively, 2n and 2m for each subsequence of the two strings, and then O(Max (m,n)) is required for comparison, so that the total complexity reaches O(2m+n x Max (m,n)).

So let’s look at dynamic programming.

We use an array dp[I][j], representing the length of the LCS before the I bit of string A and the j bit of string B (starting from 1). For example, dp[4][5] represents the length of the LCS of “sads” and “admin”. A[I] B[j] A[I] B[j]

  • If A[I] == B[j], then the LCS of strings A and B is increased by one bit, i.edp[i][j] = dp[i-1][j-1]+1.
  • If A [I]! = B[j], then the LCS before the I bit of string A and the j bit of string B cannot be extended, sodp[i][j]Will inheritDp [j] and [I - 1] dp [I] [1]The medium greater value, i.edp[i][j] = max(dp[i-1][j],dp[i][j-1]).

Thus, the state transition equation can be obtained:

if(A[i] == B[j]) dp[i][j] = dp[i-1][j-1]

if(A[i] ! = B[j]) dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Where, if the length of a string is 0, then the LCS must be 0, so there is a boundary:

dp[i][0] = dp[0][j] = 0

Thus, the state dp[I][j] is only related to its previous state, and the entire DP array can be obtained from the boundary. Finally, dp[n][m] is the required answer, and the time complexity is O (Mn).

The code implementation is as follows:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100;
char A[N], B[N];	// Store a string
int dp[N][N];			

int main(a) {
  int n;
  gets(A + 1);
  gets(B + 1);
  int lenA = strlen(A + 1);
  int lenB = strlen(B + 1);
  // Initialize the boundary
  for(int i = 0; i <= lenA; i++) {
    dp[i][0] = 0;
  }
  for(int i = 0; i <= lenB; i++) {
    dp[0][j] = 0;
  }
  // State transition equation
  for(int i = 1; i <= lenA; i++) {
    for(int j = 1; j <= lenB; j++) {
      if(A[i] == B[j]) {
        dp[i][j] = dp[i- 1][j- 1] + 1;
      }else {
        dp[i][j] = max(dp[i- 1][j], dp[i][j- 1]); }}}// dp[lenA][lenB
  printf("%d\n", dp[lenA][lenB]);
  return 0;
}

/* input: sadstory adminsorry output: 6 */
Copy the code