Subșir comun maxim: LCS și reconstruire în C++

Un subșir păstrează ordinea caracterelor, dar poate omite poziții. Pentru două texte, căutăm un subșir comun de lungime maximă, numit LCS. Nu cerem un fragment consecutiv și nu avem voie să sortăm literele înainte de comparare.

Pentru abcde și ace, răspunsul ace are lungimea trei, deși în primul text literele nu sunt consecutive. Vom calcula atât lungimea maximă, cât și un subșir care o atinge. Dacă există mai multe soluții optime, este suficientă una.

Cum funcționează

Definim d[i][j] ca lungimea maximă a unui subșir comun pentru primele i caractere din a și primele j caractere din b. Indicii i și j exprimă lungimi de prefixe. Ultimele caractere ale lor sunt a[i-1] și b[j-1], deoarece textele sunt indexate de la zero.

Dacă i=0 sau j=0, unul dintre prefixe este vid și lungimea comună este zero. Aceste baze formează linia și coloana zero. Pentru caractere finale egale, le putem potrivi la capătul unei soluții pentru prefixele mai scurte: d[i][j]=d[i-1][j-1]+1.

Dacă ultimele caractere diferă, nu le putem potrivi între ele. Cel puțin unul dintre ele nu este folosit într-o soluție optimă. Comparăm omiterea ultimului caracter din a, cu valoarea d[i-1][j], și omiterea celui din b, cu valoarea d[i][j-1]. Luăm maximul. Nu resetăm starea la zero: acesta ar fi un model pentru fragmente consecutive, nu pentru subșiruri.

Construim tabelul pe linii. La reconstruire pornim de la (n,m). Dacă ultimele caractere sunt egale, memorăm caracterul și mergem pe diagonală. Altfel mergem către un vecin care păstrează lungimea optimă. La egalitate alegem vecinul de sus. Caracterele sunt descoperite de la sfârșitul subșirului către început și se afișează invers.

Intrarea conține două linii cu câte 0..200 de litere mici a-z. Liniile vide sunt permise. Afișăm lungimea pe prima linie și subșirul pe a doua. Varianta clasică folosește char[201], suficient pentru 200 de litere și terminatorul nul. std::cin.getline citește inclusiv o linie vidă; operatorul >> nu ar păstra acest caz în același mod.

În varianta modernă, std::string înlocuiește tabloul de caractere, std::getline înlocuiește metoda de citire cu capacitate explicită, size înlocuiește strlen, iar push_back adaugă caracterele reconstruite. Tabelul int[201][201] devine un std::vector de n+1 linii și m+1 coloane. Limitele problemei, bazele și indexarea rămân identice.

Exemplu urmărit pas cu pas

Pentru a=abc și b=ac, prefixul vid este notat cu un punct:

       .  a  c
.      0  0  0
a      0  1  1
b      0  1  1
c      0  1  2

În celula finală, c coincide cu c: luăm 1+1=2 de pe diagonală. Reconstruirea găsește mai întâi c, apoi omite b și găsește a. Afișarea inversă produce ac. Pentru ab și ba există două răspunsuri de lungime unu; regula de egalitate a programului selectează a.

Implementare C++17

Varianta cu char[] și tabel clasic:

#include <algorithm>
#include <cstring>
#include <iostream>
int main() {
    char a[201], b[201], answer[201];
    std::cin.getline(a, 201);
    std::cin.getline(b, 201);
    int n = std::strlen(a), m = std::strlen(b);
    int d[201][201] = {};
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i - 1] == b[j - 1])
                d[i][j] = d[i - 1][j - 1] + 1;
            else
                d[i][j] = std::max(d[i - 1][j], d[i][j - 1]);
    int i = n, j = m, count = 0;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            answer[count++] = a[i - 1];
            --i;
            --j;
        } else if (d[i - 1][j] >= d[i][j - 1])
            --i;
        else
            --j;
    }
    answer[count] = '\0';
    std::cout << d[n][m] << '\n';
    for (int k = count - 1; k >= 0; --k)
        std::cout << answer[k];
    std::cout << '\n';
}

Varianta cu std::string și std::vector, pentru aceleași intrări:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
    std::string a, b, answer;
    std::getline(std::cin, a);
    std::getline(std::cin, b);
    int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
    std::vector<std::vector<int>> d(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i - 1] == b[j - 1])
                d[i][j] = d[i - 1][j - 1] + 1;
            else
                d[i][j] = std::max(d[i - 1][j], d[i][j - 1]);
    int i = n, j = m, count = 0;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            answer.push_back(a[i - 1]);
            ++count;
            --i;
            --j;
        } else if (d[i - 1][j] >= d[i][j - 1])
            --i;
        else
            --j;
    }
    std::cout << d[n][m] << '\n';
    for (int k = count - 1; k >= 0; --k)
        std::cout << answer[k];
    std::cout << '\n';
}

De ce funcționează și cât costă

Când ultimele caractere diferă, o potrivire comună nu le poate folosi pe amândouă ca ultime elemente, deci unul trebuie omis. Când sunt egale, există o soluție optimă care le potrivește la final; eliminarea acestei perechi lasă subproblema diagonală. Bazele și inducția după lungimile prefixelor justifică recurența.

Timpul și memoria tabelului sunt O(n*m). Reconstruirea face cel mult n+m pași și păstrează cel mult min(n,m) caractere. Memoria poate fi redusă pentru calculul lungimii, dar simpla compresie la două linii nu păstrează întregul traseu folosit aici.

Greșeli frecvente

Nu confunda subșirul cu un fragment consecutiv. Nu accesa a[i] pentru prefixul de lungime i și nu afișa direct ordinea inversă a caracterelor reconstruite. Egalitatea dintre două lungimi optime nu demonstrează că există un singur subșir optim.

Exersează

Găsește un subșir comun maxim pentru aaaa și aa. Apoi explică diferența dintre LCS și fragment comun consecutiv pentru abcde și ace.

Rezolvare explicată: Pentru aaaa și aa, lungimea maximă este doi și răspunsul este aa. Pentru abcde și ace, LCS este ace, de lungime trei; cel mai lung fragment comun consecutiv are numai un caracter.

Probleme de practică

Rezolvă cele trei probleme în ordinea de mai jos. Deschide fiecare problemă, scrie soluția și verific-o folosind testele locale din pagină. Respectă formatul de intrare, limitele și ieșirea cerută; acestea pot diferi de programul din lecție. Trimiterea pentru punctaj necesită autentificare și un evaluator activ.

1. Litere în aceeași ordine. Calculează lungimea subșirului comun maxim. În această problemă nu trebuie să afișezi subșirul reconstruit.

2. Cel mai lung fragment comun. Variație: literele trebuie să fie consecutive în ambele cuvinte. Regândește starea și ce se întâmplă la nepotrivire; recurența LCS nu se poate copia neschimbată.

3. În câte moduri păstrăm cuvântul?. Extensie: numără alegerile de poziții care formează un cuvânt dat, în loc să maximizezi lungimea. Două alegeri diferite de poziții se numără separat.

Continuă să înveți

Înapoi la programarea dinamică. Recapitulează tablourile și recursivitatea.

Întrebări frecvente

De ce folosim prefixe în stare?

Ele delimitează exact caracterele care pot participa la soluție. Omiterea ultimului caracter produce imediat o subproblemă mai mică.

Pot apărea litere egale de mai multe ori?

Da. Pozițiile trebuie să fie distincte și în ordine. Aceeași poziție nu poate fi folosită de două ori, dar caractere egale din poziții diferite pot participa.

De ce nu sortăm textele?

Sortarea distruge ordinea originală. Am obține o problemă despre frecvențe de caractere, nu despre subșiruri comune.

Este soluția afișată minimă lexicografic?

Nu. Regula locală de egalitate produce o soluție optimă ca lungime, fără această garanție suplimentară.

Cum verific subșirul reconstruit?

Parcurge separat fiecare text și caută caracterele răspunsului în ordine, fără să revii la poziții anterioare. Lungimea lui trebuie să fie egală cu d[n][m].