Розбір

The subsequence of a given sequence is a set of elements arranged in the same order as in the original sequence but not necessarily contiguous. A subsequence can be obtained from the original sequence by removing some of its elements.

For example, consider the sequence ${2, 1, 3, 5}$ . Then

${1, 5}, {2}, {2, 3, 5}$ are subsequences;
${5, 1}, {2, 3, 1}$ are not subsequences;

The common subsequence of two sequences is a subsequence that appears in both sequences.

The longest common subsequence (LCS) is a common subsequence of maximum length.

For example, the longest common subsequence of the sequences ${1, 2, 3}$ and ${2, 1, 3, 5}$ can be ${1, 3}$ or ${2, 3}$ . In this case, the length of the LCS is $2$ .

Let $f (i, j)$ be the length of the longest common subsequence of the sequences $x_{1} x_{2} \dots x_{i}$ and $y_{1} y_{2} \dots y_{j}$ .

If $x_{i} \neq = y_{j}$ , the LCS should be found among two options:

the prefixes $x_{1} x_{2} \dots x_{i}$ and $y_{1} y_{2} \dots y_{j - 1}$ (their LCS is $f (i, j - 1)$ ),
the prefixes $x_{1} x_{2} \dots x_{i - 1}$ and $y_{1} y_{2} \dots y_{j}$ (their LCS is $f (i - 1, j)$ ).

Return the maximum of these values:

f (i, j) = ma x (f (i, j -1), f (i -1, j))

If $x_{i} = y_{j}$ , add the current element $x_{i}$ to the LCS and consider the shorter prefixes $x_{1} x_{2} \dots x_{i - 1}$ and $y_{1} y_{2} \dots y_{j - 1}$ :

f (i, j) = 1 + f (i -1, j -1)

If one of the sequences is empty, then their LCS is also empty:

f (0, j) = f (i, 0) = 0

The recurrence relation for computing the LCS length is as follows:

f (i, j) = ⎩ ⎨ ⎧ ma x (f (i, j - 1), f (i - 1, j)), x_{i} \neq = y_{j} f (i - 1, j - 1) + 1, x_{i} = y_{j} 0, i = 0 or j = 0

Let’s consider an example of the calculations:

The values of $f (i, j)$ will be stored in an array $m [0..1000, 0..1000]$ , where $m [0] [i] = m [i] [0] = 0$ . Each subsequent row of the array $m [i] [j]$ is computed based on the previous one. Thus, to find the result, it is sufficient to store only two rows of length $1000$ in memory.

Example

Let $X = ab c d g h, Y = a e df h r$ . The longest common subsequence is $a d h$ , and its length is $f (6, 6) = 3$ .

$f (6, 6) = ma x (f (6, 5), f (5, 6)) = ma x (2, 3) = 3$ , because $Y [6] = r \neq = h = X [6]$ .

$f (5, 6) = 1 + f (4, 5) = 1 + 2 = 3$ , because $Y [5] = h = X [6]$ .

Exercise

Fill the following table:

Algorithm implementation

The arrays $x$ and $y$ contain the input sequences, and $n$ and $m$ are their lengths. The array $ma s$ stores the last two rows of dynamic computations.

#define SIZE 1010
int x[SIZE], y[SIZE], mas[2][SIZE];

The main part of the program. Read the input sequences into the arrays, starting from the first index, i.e., into the cells $x [1.. n]$ and $y [1.. m]$ .

scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&x[i]);
scanf("%d",&m);
for(i = 1; i <= m; i++) scanf("%d",&y[i]);

Initialize the array $ma s$ with zeros.

memset(mas,0,sizeof(mas));

Compute the values of the function $f (i, j)$ . Initially $ma s [0] [j]$ contains the values $f (0, j) = 0$ . Next, $ma s [1] [j]$ is used to store the values $f (1, j)$ .

Since computing $f (2, j)$ only requires the values from the previous row of the mas array, the values of $f (2, j)$ can be stored in $ma s [0] [j]$ , the values of $f (3, j)$ in $ma s [1] [j]$ and so on.

for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
  if (x[i] == y[j]) 
    mas[i%2][j] = 1 + mas[(i+1)%2][j-1];
  else 
    mas[i%2][j] = max(mas[(i+1)%2][j],mas[i%2][j-1]);

Print the answer, which is stored in $ma s [n] [m]$ . The first argument is computed modulo $2$ .

printf("%d\n",mas[n%2][m]);

Algorithm implementation — recursion

#include <stdio.h> 
#include <string.h> 
#define SIZE 1002

int x[SIZE], y[SIZE], dp[SIZE][SIZE];
int n, m, i, j, res;

int max(int i, int j)
{
  return (i > j) ? i : j;
}

int lcs(int *x, int *y, int m, int n)
{
  if (m == 0 || n == 0)
    return 0;
  if (dp[m][n] != -1) return dp[m][n];

  if (x[m] == y[n])
    return dp[m][n] = 1 + lcs(x, y, m - 1, n - 1);
  else
    return dp[m][n] = max(lcs(x, y, m, n - 1), lcs(x, y, m - 1, n));
}

int main(void)
{
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &x[i]);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) scanf("%d", &y[i]);

  memset(dp, -1, sizeof(dp));
  res = lcs(x, y, n, m);
  printf("%d\n", res);
  return 0;
}

Java implementation

import java.util.*;

public class Main
{
  static int x[], y[], dp[][];
  static int n, m;
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    x = new int[n+1];
    for(int i = 1; i <= n; i++)
      x[i] = con.nextInt();
		
    m = con.nextInt();
    y = new int[m+1];
    for(int i = 1; i <= m; i++)
      y[i] = con.nextInt();
		
    dp = new int[2][m+1];

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      if (x[i] == y[j]) 
        dp[i%2][j] = 1 + dp[(i-1)%2][j-1];
      else 
        dp[i%2][j] = Math.max(dp[(i-1)%2][j],dp[i%2][j-1]);

    System.out.println(dp[n%2][m]);
    con.close();
  }
}

Java implementation — recursion

import java.util.*;

public class Main
{
  static int x[], y[], dp[][];
  static int n, m;
	
  public static int lcs(int m, int n)
  {
    if (m == 0 || n == 0)
      return 0;
    if (dp[m][n] != -1) return dp[m][n];

    if (x[m] == y[n])
      return dp[m][n] = 1 + lcs(m - 1, n - 1);
    else
      return dp[m][n] = Math.max(lcs(m, n - 1), lcs(m - 1, n));
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    x = new int[n+1];
    for(int i = 1; i <= n; i++)
      x[i] = con.nextInt();
		
    m = con.nextInt();
    y = new int[m+1];
    for(int i = 1; i <= m; i++)
      y[i] = con.nextInt();
		
    dp = new int[n+1][m+1];
    for(int i = 0; i <= n; i++)
      Arrays.fill(dp[i], -1);

    int res = lcs(n,m);
    System.out.println(res);
    con.close();
  }
}