Найбільша спільна підпослідовність#1618

Найбільша спільна підпослідовність (Розбір)

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}$ \{2, 1, 3, 5\}. Then

${1, 5}, {2}, {2, 3, 5}$ \{1, 5\}, \{2\}, \{2, 3, 5\} are subsequences;
${5, 1}, {2, 3, 1}$ \{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}$ \{1, 2, 3\} and ${2, 1, 3, 5}$ \{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)$ f(i, j) be the length of the longest common subsequence of the sequences $x_{1} x_{2} \dots x_{i}$ x_1x_2 \ldots x_i and $y_{1} y_{2} \dots y_{j}$ y_1y_2 \ldots y_j.

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

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

Return the maximum of these values:

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

f(i, j) = max( f(i, j – 1), f(i – 1, j) )

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

f (i, j) = 1 + f (i -1, 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

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

f(i, j) = \begin{cases} max(f(i, j - 1), f(i - 1, j)), x_i \ne y_j \\ f(i - 1, j - 1) + 1, x_i = y_j\\ 0, i = 0~or~j = 0 \end{cases}

Let’s consider an example of the calculations:

The values of $f (i, j)$ f(i, j) will be stored in an array $m [0..1000, 0..1000]$ , where $m [0] [i] = m [i] [0] = 0$ 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$ X = abcdgh, Y = aedfhr. The longest common subsequence is $a d h$ , and its length is $f (6, 6) = 3$ f(6, 6) = 3.

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

$f (5, 6) = 1 + f (4, 5) = 1 + 2 = 3$ f(5, 6) = 1 + f(4, 5) = 1 + 2 = 3, because $Y [5] = h = X [6]$ 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];

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)$ f(i, j). Initially $ma s [0] [j]$ mas[0][j] contains the values $f (0, j) = 0$ f(0, j) = 0. Next, $ma s [1] [j]$ mas[1][j] is used to store the values $f (1, j)$ f(1, j).

Since computing $f (2, j)$ f(2, j) only requires the values from the previous row of the mas array, the values of $f (2, j)$ f(2, j) can be stored in $ma s [0] [j]$ mas[0][j], the values of $f (3, j)$ f(3, j) in $ma s [1] [j]$ mas[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;
}

C++

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

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();
  }
}

Java

Python implementation

Read the input sequences into lists $x$ and $y$ .

n = int(input())
x = [0] + list(map(int, input().split()))

m = int(input())
y = [0] + list(map(int, input().split()))

Initialize the list $d p$ , which contains the last two rows of the dynamic transformation.

dp = [[0] * (m + 1) for _ in range(2)]

Compute the values of $f (i, j) (1 \leq i \leq n, 1 \leq j \leq m)$ f(i, j)~(1 \le i \le n, 1 \le j \le m). Store the results of $f (i, j)$ f(i, j) in the cells $d p [i %2] [j]$ dp[i \% 2][j].

for i in range(1, n + 1):
  for j in range(1, m + 1):
    if x[i] == y[j]:
      dp [i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
    else:
      dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1])

Print the result, which is located in the cell $d p [n] [m]$ . The first argument is computed modulo $2$ .

print(dp[n % 2][m])