НСП-2#4260

НСП-2 (Həll təhlili)

Məsələdə iki sətirin ən uzun ümumi alt ardıcıllığını (ƏUAA) tapmaq və onu çap etmək lazımdır.

$d p$ massivini quracağıq, burada $d p [i] [j]$ dp[i][j] $x_{[1 \dots i]}$ x_{[1 \ldots i]} və $y_{[1 \dots j]}$ y_{[1 \ldots j]} sətirlərinin ƏUAA uzunluğuna bərabərdir. $d p [n] [m]$ dəyəri orijinal sətirlərin ƏUAA uzunluğuna bərabər olacaq ( $∣ x ∣ = n, ∣ y ∣ = m$ |x| = n, |y| = m).

$d p$ massivini hesabladıqdan sonra $d p$ matrisində $(n, m)$ hüceyrəsindən $(0, 0)$ -a doğru tərs keçərək ƏUAA-nı bərpa edirik. Cari mövqe $(i, j)$ üçün aşağıdakı addımları yerinə yetiririk:

əgər $x_{i}$ x_i və $y_{j}$ y_j simvolları eynidirsə, bu simvol ƏUAA-ya daxil edilməlidir. Onu nəticə sətirinə $r es$ əlavə edirik və $(i - 1, j - 1)$ (i - 1, j - 1) hüceyrəsinə keçirik, bu da $x_{[1 \dots i - 1]}$ x_{[1 \ldots i - 1]} və $y_{[1 \dots j - 1]}$ y_{[1 \ldots j - 1]} sətirləri üçün ƏUAA-nı qurmağa davam edir.
əgər $x_{i}$ x_i və $y_{j}$ y_j simvolları fərqlidirsə, daha böyük dəyərə sahib olan $(i, j - 1)$ (i, j - 1) və ya $(i - 1, j)$ (i - 1, j) hüceyrəsinə keçirik. Əgər $d p [i - 1] [j]$ dp[i - 1][j] və $d p [i] [j - 1]$ dp[i][j - 1] hüceyrələrindəki dəyərlər bərabərdirsə, istənilən birinə keçid mümkündür.

Nəticə sətiri $r es$ $x$ və $y$ sətirlərinin ən uzun ümumi alt ardıcıllığını özündə saxlayacaq.

Misal

Misalda verilən iki sətir üçün ən uzun ümumi alt ardıcıllığın (ƏUAA) tapılmasını nəzərdən keçirək.

Ümumi alt ardıcıllığın axtarışı $(i, j) = (6, 7)$ (i, j) = (6, 7) mövqeyindən başlayır.

$y [6] \neq = x [7]$ y[6] \ne x[7]: maksimum dəyərə sahib qonşu hüceyrələrdən birinə keçirik, məsələn, $(5, 7)$ .

$y [5] \neq = x [7]$ y[5] \ne x[7]: $(5, 6)$ -ya keçirik.

$y [5] = x [6] =$ y[5] = x[6] = ' $b$ ': diaqonal üzrə keçid edirik və ' $b$ ' hərfini ƏUAA-ya daxil edirik.

Alqoritmin reallaşdırılması

Giriş sətirlərini $x$ və $y$ elan edirik. Onların ƏUAA-nı tapmaq üçün $d p$ massivindən istifadə edirik.

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

Giriş sətirlərini oxuyuruq və onlara ön tərəfdən boşluq əlavə edirik ki, indeksləşmə $1$ -dən başlasın.

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

ƏUAA-nı tapırıq.

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$ sətirində ƏUAA-nı qururuq.

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++

Nəticə sətirini tərs çevirir və çıxışa veririk.

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