НСП - 2#4260

НСП - 2 (Розбір)

В задачі слід знайти найбільшу спільну підпослідовність (НОП) двох рядків і вивести її.

Побудуємо масив $d p$ , де $d p [i] [j]$ dp[i][j] дорівнює довжині НОП рядків $x_{[1 \dots i]}$ x_{[1 \ldots i]} і $y_{[1 \dots j]}$ y_{[1 \ldots j]}. Значення $d p [n] [m]$ буде дорівнювати довжині НОП початкових рядків ( $∣ x ∣ = n, ∣ y ∣ = m$ |x| = n, |y| = m).

Після обчислення масиву $d p$ відновимо НОП, здійснивши зворотний прохід по матриці $d p$ від комірки $(n, m)$ до $(0, 0)$ . Для поточної позиції $(i, j)$ виконуємо наступні кроки:

якщо символи $x_{i}$ x_i і $y_{j}$ y_j збігаються, цей символ має бути включений в НОП. Додаємо його в результуючий рядок $r es$ і переходимо до комірки $(i - 1, j - 1)$ (i - 1, j - 1), тобто продовжуємо будувати НОП для рядків $x_{[1 \dots i - 1]}$ x_{[1 \ldots i - 1]} і $y_{[1 \dots j - 1]}$ y_{[1 \ldots j - 1]}.
якщо символи $x_{i}$ x_i і $y_{j}$ y_j різні, то переходимо до комірки $(i, j - 1)$ (i, j - 1) або $(i - 1, j)$ (i - 1, j), вибираючи ту, де значення більше. Якщо значення в комірках $d p [i - 1] [j]$ dp[i - 1][j] і $d p [i] [j - 1]$ dp[i][j - 1] рівні, перехід можливий в будь-яку з них.

Результуючий рядок $r es$ буде містити найбільшу спільну підпослідовність рядків $x$ і $y$ .

Приклад

Розглянемо процес знаходження найбільшої спільної підпослідовності (НОП) для двох рядків, наведених у прикладі.

Пошук спільної підпослідовності починається з позиції $(i, j) = (6, 7)$ (i, j) = (6, 7).

$y [6] \neq = x [7]$ y[6] \ne x[7]: переходимо в будь-яку сусідню комірку з максимальним значенням, наприклад, до $(5, 7)$ .

$y [5] \neq = x [7]$ y[5] \ne x[7]: рухаємося до $(5, 6)$ .

$y [5] = x [6] =$ y[5] = x[6] = ' $b$ ': здійснюємо перехід по діагоналі і включаємо букву ' $b$ ' у НОП.

Реалізація алгоритму

Оголосимо вхідні рядки $x$ і $y$ . Для знаходження їх НОП використовуємо масив $d p$ .

#define MAX 1001
int dp[MAX][MAX];
string x, y, res;

Читаємо вхідні рядки і додаємо до них пробіл спереду, щоб індексація починалася з $1$ .

cin >> x; n = x.length(); x = " " + x;
cin >> y; m = y.length(); y = " " + y;

Знаходимо НОП.

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

У рядку $r es$ будуємо НОП.

i = n; j = m;
while (i >= 1 && j >= 1)
  if (x[i] == y[j])
  {
    res = res + x[i];
    i--; j--;
  }
  else
  {
    if (dp[i - 1][j] > dp[i][j - 1])
      i--;
    else
      j--;
  }

C++

Звертаємо і виводимо результуючий рядок.

reverse(res.begin(), res.end());
cout << res << endl;