Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie najdłuższego wspólnego podciągu

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Dla danych dwóch niepustych łańcuchów tekstowych s1s2 należy wyznaczyć najdłuższy wspólny podciąg znakowy.


Na pierwszy rzut oka problem wydaje się taki sam jak w poprzednim rozdziale. Jest jednak bardzo istotna różnica. Przy znajdowaniu najdłuższego wspólnego podłańcucha chodziło o znalezienie najdłuższego, spójnego fragmentu tekstu, który występuje w obu łańcuchach. W bieżącym problemie znajdowania najdłuższego wspólnego podciągu (ang. longest common subsequence) chodzi o wyznaczenie najdłuższego ciągu znaków, które występują w tej samej kolejności w obu łańcuchach. Znaki te mogą być rozdzielone w każdym z łańcuchów innymi znakami.

Przykład:

Najdłuższy wspólny podłańcuch Najdłuższy wspólny podciąg
s1 = ALIBABA
s2 = KALIMALBA
s1 = ALIBABA
s2 = KALIMALBA
ALI ALIABA

Problem znajdowania najdłuższego wspólnego podciągu występuje we wielu dziedzinach nauki:

  • Biologia molekularna – badania ciągów genów w łańcuchach DNA, które można sprowadzić do długich łańcuchów tekstowych zbudowanych z czterech znaków ACGT reprezentujących składniki DNA. Gdy zostaną znalezione nowe ciągi aminokwasów, szuka się podobieństw do nich. Do tego celu właśnie służy znajdowanie najdłuższych wspólnych podciągów.
  • Porównywanie plików – można sprawdzić w jakim stopniu dwa różne pliki są do siebie podobne wydzielając w nich najdłuższy wspólny podciąg.

Rozwiązanie nr 1

W pierwszym podejściu zastosujemy nieefektywne rozwiązanie rekurencyjne. Zaobserwujmy kilka prostych faktów związanych z problemem najdłuższego wspólnego podciągu – nazwijmy go dla ułatwienia LCS (ang. longest common subsequence). Załóżmy, iż mamy dwa łańcuchy znaków takie jak w powyższym przykładzie. Zapiszmy je jeden nad drugim i połączmy strzałkami znaki należące do LCS:

obrazek

Zwróć uwagę, iż strzałki nie mogą się krzyżować, gdyż wtedy nie byłaby zachowana kolejność znaków. Wynika stąd kilka bardzo istotnych wniosków:

Jeśli dwa łańcuchy rozpoczynają się od tego samego znaku, to znak ten na pewno należy do LCS.

Jeśli początkowe znaki w obu łańcuchach są różne, to nie mogą oba jednocześnie należeć do LCS, gdyż wymagałoby to skrzyżowania strzałek. Jeden z nich (a może oba) będzie trzeba usunąć. Gdy zdecydujemy, co z nimi zrobić, to problem zredukuje się do znalezienia najdłuższego wspólnego podciągu dla łańcuchów pomniejszonych o te pierwsze znaki. Pozwala to na rozwiązanie rekurencyjne. Na początek określimy algorytm znajdowania długości LCS, a następnie samego LCS.

Algorytm rekurencyjnego znajdowania długości najdłuższego wspólnego podciągu

Wejście:

s1, s2 : łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.
i : indeks s1, od którego rozpoczynamy przeglądanie łańcucha; i ∈ N.
j : indeks s2, od którego rozpoczynamy przeglądanie łańcucha; j ∈ N.

Wyjście:

Długość LCS ∈ N.

Lista kroków LCS(i,j):

K01: Jeśli s1[i] = wartownik, ; napotkany koniec łańcucha s1
     to zakończ z wynikiem 0
K02: Jeśli s2[j] = wartownik, ; napotkany koniec łańcucha s2
     to zakończ z wynikiem 0
K03: Jeśli s1[i] = s2[j], ; wywołanie rekurencyjne
to zakończ z wynikiem 1+LCS(i+1,j+1)
K04: Zakończ z wynikiem max(LCS(i+1,j),LCS(i,j+1))
     ; wywołanie rekurencyjne

Mając algorytm znajdowania długości LCS możemy skonstruować algorytm wyznaczania samego LCS. Opieramy się na następujących przesłankach:

Jeśli znaki s1[i] oraz s2[j] są równe, to należą do LCS.
Jeśli znaki s1[i] oraz s2[j] są różne, to wyliczamy LCS(i+1,j) oraz LCS(i,j+1), a następnie sprawdzamy:

  1. LCS(i+1,j) ≤ LCS(i,j+1) –  odrzucamy s2[j], gdyż bez niego mamy dłuższy LCS.
  2. Inaczej odrzucamy s1[i] z tego samego powodu co wyżej.

Algorytm znajdowania najdłuższego wspólnego podciągu

Wejście:

s1, s2 : łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika o kodzie 0 (w C++ już jest!).
i : indeks w s1, od którego rozpoczynamy przeglądanie łańcucha; i ∈ N.
j : indeks w s2, od którego rozpoczynamy przeglądanie łańcucha; j ∈ N.

Wyjście:

Zawartość sLCS

Zmienne pomocnicze:

sLCS : łańcuch zawierający LCS

Lista kroków:

K01: sLCS ← "" ; zerujemy LCS
K02: i ← 0 ; ustawiamy indeksy na pierwszych znakach s1 i s2
K03: j ← 0
K04: Dopóki (s1[i] ≠ 0) ∧ (s2[j] ≠ 0):
     wykonuj kroki K05…K11
K05:   Jeśli s1[i] ≠ s2[j], ; sprawdzamy równość znaków w obu łańcuchach
       idź do kroku K10
K06:   sLCSsLCS + s1[i] ; dodajemy znak do LCS
K07:   ii + 1 ; przesuwamy się na następną pozycję w obu łańcuchach
K08:   jj + 1
K09:   Następny obieg pętli K04 ; i kontynuujemy pętlę
K10:   Jeśli LCS(i+1,j) ≤ LCS(i,j+1), ; odrzucamy znak s2[j]
       to idź do kroki K08
K11:   ii + 1 ; odrzucamy znak s1[i]
K12: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje dwa wiersze znaków (niezbyt długie z uwagi na wykładniczą klasę złożoności algorytmu), znajduje dla nich najdłuższy wspólny podciąg, wypisuje go wraz z jego długością.
Pascal
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

uses Math;

var
  s1, s2, sLCS : ansistring;

// Funkcja oblicza długość LCS dla s1 i s2
// i - indeks startu w s1
// j - indeks startu w s2
//----------------------------------------
function LCS (i, j : integer) : integer;
begin
  if(s1[i] = #0) or (s2[j] = #0) then
    LCS := 0
  else if s1[i] = s2[j] then
    LCS := 1+LCS(i+1,j+1)
  else
    LCS := max(LCS(i+1,j),LCS(i,j+1));
end;

var
  i, j : integer;

begin
  readln(s1); readln(s2);
  s1 := s1 + #0; // wartownik
  s2 := s2 + #0; // wartownik
  sLCS := ''; i := 1; j := 1;
  while(s1[i] <> #0) and (s2[j] <> #0) do
    if s1[i] = s2[j] then
    begin
      sLCS := sLCS + s1[i];
      inc(i); inc(j);
    end
    else if LCS(i+1,j) <= LCS(i,j+1) then inc(j) else inc(i);
  writeln(sLCS, ' : ', length(sLCS));
end.
C++
// Wyszukiwanie najdłuższego wspólnego podciągu
// Data: 17.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

string s1, s2, sLCS; // zmienne globalne

// Funkcja oblicza długość LCS dla s1 i s2
// i - indeks startu w s1
// j - indeks startu w s2
//----------------------------------------
int LCS (int i, int j)
{
  if(!s1[i] || !s2[j]) return 0;
  else if(s1[i] == s2[j]) return 1+LCS(i+1,j+1);
  else return max(LCS(i+1,j),LCS(i,j+1));
}

int main()
{
  int i, j;

  getline(cin,s1);
  getline(cin,s2);
  sLCS = ""; i = j = 0;
  while(s1[i] && s2[j])
    if(s1[i] == s2[j])
    {
      sLCS += s1[i]; i++; j++;
    }
    else if(LCS(i+1,j) <= LCS(i,j+1)) j++; else i++;
  cout << sLCS << ": " << sLCS.length() << endl;
  return 0;
}
Basic
' Wyszukiwanie najdłuższego wspólnego podciągu
' Data: 17.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim Shared As String s1, s2

' Funkcja zwraca większy ze swoich argumentów
'--------------------------------------------
Function max (Byval x As Integer,_
              Byval y As Integer)_
              As Integer
  If x > y Then
    max = x
  Else
    max = y
  End If
End Function

' Funkcja oblicza długość LCS dla s1 i s2
' i - indeks startu w s1
' j - indeks startu w s2
'----------------------------------------
Function LCS (Byval i As Integer,_
              Byval j As Integer)_
              As Integer
  if(Mid(s1,i,1) = Chr(0)) Or (Mid(s2,j,1) = Chr(0)) Then
    LCS = 0
  Elseif Mid(s1,i,1) = Mid(s2,j,1) Then
    LCS = 1 + LCS(i+1,j+1)
  Else
    LCS = max(LCS(i+1,j),LCS(i,j+1))
  End If
End Function

Dim As String sLCS
Dim As Integer i, j

Line Input s1: Line Input s2
s1 += Chr(0) ' wartownik
s2 += Chr(0) ' wartownik
sLCS = "": i = 1: j = 1
while(Mid(s1,i,1) <> Chr(0)) And (Mid(s2,j,1) <> Chr(0))
  If Mid(s1,i,1) = Mid(s2,j,1) Then
    sLCS += Mid(s1,i,1)
    i += 1: j += 1
  ElseIf LCS(i+1,j) <= LCS(i,j+1) Then
    j += 1
  Else
    i += 1
  End If
Wend
Print sLCS;": ";Len(sLCS)
End
Python (dodatek)
# Wyszukiwanie najdłuższego wspólnego podciągu
# Data: 17.03.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

# zmienne globalne

s1 = ""
s2 = ""
sLCS = ""

# Funkcja oblicza długość LCS dla s1 i s2
# i - indeks startu w s1
# j - indeks startu w s2
#----------------------------------------

def LCS(i,j):
    if not ord(s1[i]) or not ord(s2[j]): return 0
    elif s1[i] == s2[j]: return 1+LCS(i+1,j+1)
    else: return max(LCS(i+1,j),LCS(i,j+1))

s1 = input() + chr(0)
s2 = input() + chr(0)
sLCS = ""
i,j = 0,0
while ord(s1[i]) and ord(s2[j]):
    if s1[i] == s2[j]:
        sLCS += s1[i]
        i += 1
        j += 1
    elif LCS(i+1,j) <= LCS(i,j+1):
        j += 1
    else:
        i += 1
print(sLCS,":",len(sLCS))
print()
Wynik:
ALIBABA
KALIMALBA
ALIABA : 6

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

Algorytm rekurencyjny wyznaczania LCS posiada wykładniczą złożoność obliczeniową. Winę za to ponoszą rekurencyjne wywołania przy wyliczaniu długości LCS, gdzie wielokrotnie wykonywane są te same obliczenia. Usprawnienie zatem polega na eliminacji wywołań rekurencyjnych i zastosowaniu programowania dynamicznego – wyliczone długości LCS są zapamiętywane w osobnej tablicy L[(m+1) × (n+1)]. Dzięki takiemu podejściu klasa złożoności obliczeniowej spada do O(m × n), jednakże algorytm wymaga dodatkowej pamięci rzędu O(m × n). Element L[i+1,j+1] zawiera długość LCS dla podłańcuchów s1[0:i] oraz s2[0:j].

Algorytm dynamicznego znajdowania długości najdłuższego wspólnego podciągu

Wejście:

s1, s2– łańcuchy tekstowe, w których szukamy LCS. Na końcu łańcuchów dodajemy wartownika.

Wyjście:

Długość LCS. Dodatkowo efektem działania algorytmu jest wypełniona tablica L, która może posłużyć do wyznaczania znaków LCS.

Zmienne pomocnicze:

m : długość łańcucha s1; m ∈ N.
: długość łańcucha s2; n ∈ N.
L : tablica długości o indeksach od 0 do m oraz od 0 do n; L ∈ N.
i, j : indeksy znaków s1s2; i, j ∈ N.

Lista kroków:

K01: m ← |s1| ; obliczamy długości łańcuchów s1
K02: n ← |s2| ; oraz s2
K03: Dla i = 0,1,…,m: ; inicjujemy pierwszą kolumnę tablicy L
     wykonuj L[i,0] ← 0
K04: Dla j = 0,1,…,n: ; oraz pierwszy wiersz
     wykonuj L[0,j] ← 0
K05: Dla i = 0,1,…,m-1: ; wyznaczamy długości kolejnych LCS
     wykonuj kroki K06…K10
K06:   Dla j = 0,1,…,n-1:
       wykonuj kroki K07…K10
K07:   Jeśli s1[i] ≠ s2[j], ; sprawdzamy, czy LCS jest rozszerzalny
       to idź do kroku K10
K08:   L[i+1,j+1] ← 1+L[i,j] ; jeśli tak, to zwiększamy poprzednią długość
K09:   Następny obieg pętli K06
K10:   L[i+1,j+1] ← max(L[i+1,j],L[i,j+1]) ; jeśli nie, wybieramy dłuższy LCS
K11: Zakończ z wynikiem L[m,n]

Algorytm znajdowania najdłuższego wspólnego podciągu

Wejście:

s1, s2 – łańcuchy tekstowe, w których szukamy LCS.

Wyjście:

Zawartość LCS

Zmienne pomocnicze:

sLCS  :  łańcuch zawierający LCS
L  :  tablica długości LCS o indeksach od 0 do m oraz od 0 do n
i, j  :  indeksy znaków s1s2

Lista kroków:

K01: Utwórz i oblicz tablicę L ; wyznaczamy długości kolejnych LCS
K02: sLCS ← "" ; zerujemy LCS
K03: i ← m - 1 ; ustawiamy indeksy na ostatnich znakach s1 i s2
K04: j ← n - 1
K05: Dopóki (i ≥ 0) ∧ ( j ≥ 0),
     wykonuj kroki K06…K12
K06:   Jeśli s1[i] ≠ s2[j], ; sprawdzamy równość znaków w obu łańcuchach
       to idź do kroku K11
K07:   sLCSs1[i] + sLCS ; dodajemy znak na początek LCS
       ; - znaki otrzymujemy od końca!
K08:   ii - 1 ; przesuwamy się na poprzednią pozycję w obu łańcuchach
K09:   jj - 1
K10:   Następny obieg pętli K05 ; i kontynuujemy pętlę
K11:   Jeśli L[i+1,j] > L[i,j+1], ; cofamy się w s2
       to idź do kroku K09
K12:   ii - 1 ; cofamy się w s1
K13: Zakończ z wynikiem sLCS

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje dwa wiersze znaków, znajduje dla nich najdłuższy wspólny podciąg i wypisuje go wraz z jego długością.
Pascal
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

uses Math;

type
  Tint = array of integer;
  TTint = array of Tint;

var
  s1, s2, sLCS : ansistring;
  L : TTint;
  i, j, m, n : integer;

begin
  readln(s1); readln(s2);

  m  := length(s1);
  n  := length(s2);

// tworzymy dynamicznie tablicę L

  setlength(L,m+1);
  for i := 0 to m do setlength(L[i],n+1);

// obliczamy tablicę L

  for i := 0 to m do L[i][0] := 0;
  for j := 0 to n do L[0][j] := 0;
  for i := 1 to m do
    for j := 1 to n do
      if s1[i] = s2[j] then
        L[i][j] := 1+L[i-1][j-1]
      else
        L[i][j] := max(L[i][j-1],L[i-1][j]);

// wyznaczamy LCS

  sLCS := ''; i := m; j := n;
  while(i > 0) and (j > 0) do
    if s1[i] = s2[j] then
    begin
      sLCS := s1[i] + sLCS;
      dec(i); dec(j);
    end
    else if L[i][j-1] > L[i-1][j] then dec(j)
    else dec (i);
  writeln(sLCS, ' : ', L[m][n]);
end.
C++
// Wyszukiwanie najdłuższego podciągu
// Data: 18.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s1, s2, sLCS;
  int ** L, i, j, m, n;

  getline(cin,s1);
  getline(cin,s2);
 
  m  = s1.length();
  n  = s2.length();

// tworzymy dynamicznie tablicę L

  L = new int * [m+1];
  for(i = 0; i <= m; i++)
    L[i] = new int [n+1];

// obliczamy tablicę L

  for(i = 0; i <= m; i++) L[i][0] = 0;
  for(j = 0; j <= n; j++) L[0][j] = 0;
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
      if(s1[i] == s2[j])
        L[i+1][j+1] = 1+L[i][j];
      else
        L[i+1][j+1] = max(L[i+1][j],L[i][j+1]);

// wyznaczamy LCS

  sLCS = ""; i = m - 1; j = n - 1;
  while((i >= 0) && (j >= 0))
    if(s1[i] == s2[j])
    {
      sLCS = s1[i] + sLCS;
      i--; j--;
    }
    else if(L[i+1][j] > L[i][j+1]) j--;
    else i--;
  cout << sLCS << ": " << L[m][n] << endl;
  return 0;
}
Basic
' Wyszukiwanie najdłuższego podciągu
' Data: 18.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

' Funkcja zwraca większy ze swoich argumentów
'--------------------------------------------
Function max (Byval x As Integer,_
              Byval y As Integer)_
              As Integer
  If x > y Then
    max = x
  Else
    max = y
  End If
End Function

Dim As String s1, s2, sLCS
Dim As Integer i, j, m, n

Line Input s1: Line Input s2

m = Len(s1)
n = Len(s2)

' tworzymy dynamicznie tablicę L

Dim As Integer L(m,n)

' obliczamy tablicę L

For i = 0 To m
  L(i,0) = 0
Next
For j = 0 To n
  L(0,j) = 0
Next
For i = 1 To m
  For j = 1 To n
    If Mid(s1,i,1) = Mid(s2,j,1) Then
      L(i,j) = 1+L(i-1,j-1)
    Else
      L(i,j) = max(L(i,j-1),L(i-1,j))
    End If
  Next
Next

' wyznaczamy LCS

sLCS = "": i = m: j = n
while(i > 0) And (j > 0)
  If Mid(s1,i,1) = Mid(s2,j,1) Then
    sLCS = Mid(s1,i,1) + sLCS
    i -= 1: j -= 1
  Elseif L(i,j-1) > L(i-1,j) Then
    j -= 1
  Else
    i -= 1
  End If
Wend
Print sLCS;": ";L(m,n)
End
Python (dodatek)
# Wyszukiwanie najdłuższego podciągu
# Data: 18.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

s1 = input()
s2 = input()
 
m = len(s1)
n = len(s2)

# tworzymy dynamicznie tablicę L

L = []
for i in range(m+1):
    a = []
    for j in range(n+1):
        a.append(0)
    L.append(a)

# obliczamy tablicę L

for i in range(m):
    for j in range(n):
        if s1[i] == s2[j]:
            L[i+1][j+1] = 1+L[i][j]
        else:
            L[i+1][j+1] = max(L[i+1][j],L[i][j+1])

# wyznaczamy LCS

sLCS = ""
i,j = m-1,n-1
while (i >= 0) and (j >= 0):
    if(s1[i] == s2[j]):
        sLCS = s1[i] + sLCS
        i -= 1
        j -= 1
    elif L[i+1][j] > L[i][j+1]:
        j -= 1
    else:
        i -= 1
print(sLCS,":",L[m][n])

Wyszukiwanie najdłuższego wspólnego podciągu
(C)2020 mgr Jerzy Wałaszek

s1 =
s2 =


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.