Strona główna » Algorytmy » Artykuły » Najdłuższy Podciąg Dwóch Wyrażeń
 

Najdłuższy Podciąg Dwóch Wyrażeń

https://mattomatti.com/a0069

Wstęp

Wyszukiwanie najdłuższego wspólnego podciągu można rozwiązać sprawdzając wszystkie możliwe kombinacje, ale efektywność takiego algorytmu jest niewielka. Istnieje możliwość przyśpieszenia takiego wyszukiwania wykorzystując do tego programowanie dynamiczne. Dzięki temu uzyskana złożoność wynosi zaledwie O(n·m), gdzie n i m to kolejno długości wyrażenia pierwszego i drugiego.

Algorytm

Algorytm wyszukiwania najdłuższego wspólnego podciągu oparty na programowaniu dynamicznym deklaruje dodatkową tablicę m + 1 × n + 1. W dwuwymierowej tablicy przetrzymywane są tymczasowe wyniki kolejnych porównań. Dzięki temu możliwe jest na bieżąco śledzenie jak długi jest podciąg obydwu wyrażeń. Zasada wypełniania tabelki jest następuąca:

  1. Pierwszy wiersz oraz pierwszą kolumnę wypełniamy przy pomocy 0
  2. Dla każdej kolejnej komórki (i, j) wykonujemy porównanie i-tego elementu ze słowa pierwszego oraz j-tego elementu ze słowa drugiego, następnie jeśli elementy są równe to pobieramy element z tablicy tymczasowej na pozycji (i - 1, j - 1) i zwiększamy go o 1, ale jeśli elementy są różne to ustawiamy wartość komórki na 0

W wypełnionej tabelce następnie należy znaleźć największą wartość liczbową, ponieważ będzie to długość maksymalnego podciągu obydwu wyrażeń. Na tym się kończy algorytm jeśli tylko chcemy sprawdzic jak długi jest wspólny podciąg.

Jednak, aby algorytm zwrócił tekst, który jest częścią wspólną to należy wykonać jeszcze jeden etap. Znając pozycje największej wartości w tabeli znamy również pozycje liter, które były porównywane tj. największa wartość na pozycji (x, y) wskazuje literę x-ową w pierwszym wyrażeniu i y-ową w drugim. W celu wybrania wszystkich liter słowa należy przesuwać się po komórkach położonych po skosie lewo/góra, aż do napotkania wartości 0. Dla wartości 0 litery już się nie pobiera. Uwaga przepisując znaki tekstu od maksymalnej wartości do wystąpienia zwróci podciąg zapisany wspak!

Przykład

Prześledźmy działania algorytmu dla słów s1 = "KAJAKI" oraz s2 = "JAK". Jak nietrudno zauważyć drugie słowo występuje w pierszym, więc cały drugi wyraz powinien zostać wskazany jako nadłuższy podciąg obu wyrazów. Ustalamy wartośc n = 6 i m = 3 na podstawie długości wyrazów. Utwórzmy tabelkę, a następnie wypełnijmy pierwszą kolumnę oraz pierwszy wiersz samymi zerami:

i\j1234
10000
20---
30---
40---
50---
60---
70---

Teraz można przejść do porównywania elementów z obu wyrażeń. Algorytm będzie je wypełniał komórka po komórce, ale w celu zrozumienia warto przeanalizować porównania, których algorytm dokonuje. W tym celu w każdej komórce zapiszmy wykonane porównanie dla danej komórki i sprawdźmy, które porównania zwrócą prawdę:

i\j1234
10000
20s1[0] ≠ s2[0]
K ≠ J		s1[1] ≠ s2[0]
K ≠ A		s1[2] = s2[0]
K = K
30s1[0] ≠ s2[1]
A ≠ J		s1[1] = s2[1]
A = A		s1[2] ≠ s2[1]
A ≠ K
40s1[0] = s2[2]
J = J		s1[1] ≠ s2[2]
J ≠ A		s1[2] ≠ s2[2]
J ≠ K
50s1[0] ≠ s2[3]
A ≠ J		s1[1] = s2[3]
A = A		s1[2] ≠ s2[3]
A ≠ K
60s1[0] ≠ s2[4]
K ≠ J		s1[1] ≠ s2[4]
K ≠ A		s1[2] = s2[4]
K = K
70s1[0] ≠ s2[5]
I ≠ J		s1[1] ≠ s2[5]
I ≠ A		s1[2] ≠ s2[5]
I ≠ K

Kolejny etap polega na zamianie wyników prawda/fałsz na wartości liczbowe. Jeśli porównywane wartości są różne to wstawiamy 0, ale w przeciwnym wypadku należy pobrać element wiersz wyżej i kolumnę wcześniej i zwiększyć go o jeden. W trakcie wypełniania należy pamiętać, że tabelkę należy wypełniać wierszami od strony lewej do prawej:

i\j1234
10000
20001
30010
40100
50020
60003
70000

W tabelce największa wartość to 3 i dokładnie takiej długości jest najdłuższy podciąg obydwu wyrażeń. Teraz można odczytać wspólny podciąg tekstu. Wiemy, że maksymalny element znajduje się na pozycji (i, j) = (6, 4) i ma wartość 3, więc przepisujemy znak i - 1 = 5 z pierwszego słowa. Potem przechodzimy na pozycję (5, 3) o wartości 2 i przepisujemy znak 4 z pierwszego słowa. Wykonujemy to samo dla pozycji (4, 2), ale dla pozycji (3, 1) już nie, ponieważ ma ona wartość 0.

Pozycja(6, 4)(5, 3)(4, 2)(3, 1)
ZnakKAJ-

Odczytany wyraz jest zapisany wspak, więc w zależności od sposobu zapisu kolejnych liter może istnieć potrzeba zapisania go wstecz. Proces wybierania można przeprowadzić również używając współrzędnej j, ale należy wtedy pamiętać, że znaki należy wybierać z słowa drugiego. Ostatecznie wspólny podciąg ma długość 3 i jest to "JAK".

Implementacja

Funkcja do wyznaczania wspólnego podciągu najdluzszyPodciag() przyjmuje tylko dwa argumenty str1 i str2 dla którego należy wyznaczyć najdłuższy podciąg, który zostanie zwrócony jako fragment tekstu. Jeśli podciąg nie istnieje to zostanie zwrócony pusty wyraz.

C++
C#
  1. string najdluzszyPodciag(string str1, string str2) {
  2.   int n = str1.length();
  3.   int m = str2.length();
  4.   int** tab_pom = new int*[n + 1];
  5.   for (int i = 0; i <= n; i++)
  6.     tab_pom[i] = new int[m + 1];
  7.   int wynik = 0, poz = 0;
  8.   for (int i = 0; i <= n; i++) {
  9.     for (int j = 0; j <= m; j++) {
  10.       if (i == 0 || j == 0) {
  11.         tab_pom[i][j] = 0;
  12.       } else if (str1[i - 1] == str2[j - 1]) {
  13.         tab_pom[i][j] = tab_pom[i - 1][j - 1] + 1;
  14.         if (tab_pom[i][j] > wynik) {
  15.           wynik = tab_pom[i][j];
  16.           poz = i;
  17.         }
  18.       } else {
  19.         tab_pom[i][j] = 0;
  20.       }
  21.     }
  22.   }
  23.   string w = "";
  24.   for (int i = wynik; i > 0; i--)
  25.     w += str1[poz - i];
  26.   for (int i = 0; i <= n; i++)
  27.     delete tab_pom[i];
  28.   delete tab_pom;
  29.   return w;
  30. }

Na początku funkcji pobieram długość (2.) pierwszego i (3.) tekstu zapisując kolejno do zmiennych n i m. Następnie (4. - 6.) deklarujemy tablicę dwuwymiarową. Nie ma potrzeby jej zerowania. Przed rozpoczęciem wypełniania tabeli (7.) deklarujemy dwie zmienne: wynik - maksymalna wartość w tabeli oraz poz - pozycji i w tabeli najdłuższego podsłowa.

Kolejny etap polega na wypełnianiu kolejnych (8.) wierszy i (9.) kolumn wartościami. Jeśli (10.) jest to pierwszy wiersz lub kolumna to (11.) zerujemy komórkę. W przeciwnym razie (12.) porównujemy wartości. Jeśli są identyczne to (13.) pobieramy wartość z komórki na lewo do góry wiersz wcześniej i zwiększamy wartość o 1. Potem (14.) należy sprawdzić czy znaleziony podciąg nie ma długości większej niż ten, który do tej pory znaleziono. Jeśli nowy podciąg jest dłuższy to (15.) zapisz długość jak nową maksymalną wartość i (16.) zapamiętaj pozycję znaku. Jeśli oba warunki nie są spełnione to (19.) wpisz 0.

Ostatni etap wyznaczania wspólnego podciągu polega na (23.) przygotowaniu zmiennej do zapisu wyniku i (24. - 25.) odczytaniu kolejnych wartości ze słowa na podstawie pozycji maksymalnej wartości. Przed (29.) zwróceniem wyniku (26. - 28.) należy zdealokować tablicę pomocniczą.

Testowanie funkcji

W celu przetesowanie napisanej funkcji można skorzystać z poniższego fragmentu kodu. Program wczyta od użytkownika dwa słowa i znajdzie dla nich część wspólną. Jeśli jednak nie będzie istnieć to zostanie wyświetlony stosowny komunikat.

C++
C#
  1. int main() {
  2.   string str1, str2;
  3.   cout << "Podaj pierwsze wyrazenie:\n str1 = ";
  4.   cin >> str1;
  5.   cout << "Podaj drugie wyrazenie:\n str2 = ";
  6.   cin >> str2;
  7.   string w = najdluzszyPodciag(str1, str2);
  8.   if (w == "") {
  9.     cout << "Wyrazy nie maja wspolnej czesci";
  10.   } else {
  11.     cout << "Najdluzsze podslowo to: " << w << endl;
  12.   }
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Napisz algorytm, który znajdzie dla dwóch podanych wyrażeń wszystkie podciągi maksymalnego rozmiaru. Funkcja powinna zwracać wszystkie podciągi rozdzielone przecinkiem. Podciągi powinny być posortowane według kolejności występowania w pierwszy wyrażeniu. Zakładamy, że wybierane słowa mogą się powtarzać.

Przykładowo dla słów str1 = "ABCD" oraz str2 = "CDAB" program powinien wypisać:

  1. AB, CD

Przykładowo dla słów str1 = "123" oraz str2 = "321" program powinien wypisać:

  1. 1, 2, 3