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 podłańcucha

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Dla danych, niepustych łańcuchów tekstowych s1s2 należy wyznaczyć najdłuższy wspólny podłańcuch s.


W porównaniu z poprzednimi zadaniami ten problem jest dosyć trudny, ponieważ nie wiemy, czego szukamy. Nie możemy zatem w normalny sposób sprawdzić, czy to coś występuje jednocześnie w łańcuchach s1s2. Problem wyszukiwania wspólnych sekwencji symboli jest szeroko wykorzystywany w badaniach genetycznych łańcuchów DNA, które możemy potraktować jako teksty.

Rozwiązanie nr 1

Pierwsze rozwiązanie problemu wyszukiwania najdłuższego wspólnego podłańcucha (ang. the longest common substring – LCS) jest rozwiązaniem nieoptymalnym. Nasz algorytm będzie się starał dopasowywać jak największe fragmenty łańcucha s1 do fragmentów łańcucha s2 zapamiętując najdłuższy, wyznaczony w ten sposób podłańcuch. Zasada jego pracy będzie następująca:

Wybieramy kolejne znaki łańcucha s1. Wyszukujemy w s2 wszystkie wystąpienia wybranego znaku. Po znalezieniu zgodności staramy się maksymalnie rozszerzyć pasujący fragment w prawo. Długości wyznaczonych w ten sposób wspólnych podciągów tworzą ciąg liczbowy, w którym wyszukujemy wartość maksymalną. Zapamiętujemy położenie podciągu oraz jego długość. Po przetworzeniu wszystkich znaków łańcucha s1 mamy wyznaczony najdłuższy wspólny podłańcuch.

Tak określony algorytm znajdowania najdłuższego wspólnego podciągu posiada sześcienną klasę złożoności obliczeniowej O(m2 × n), gdzie m jest długością łańcucha s1, n jest długością łańcucha s2.

Przykład:

Wyszukać najdłuższy wspólny podłańcuch dla:

s1 = AAABBA
s2 = ABAABBAAA

Lp. Kolejne dopasowania s2 do s1 Najdłuższy wspólny podłańcuch
1.
                 A A A B B A
                 A B A A B B A A A
             A B A A B B A A A
           A B A A B B A A A
     A B A A B B A A A 
   A B A A B B A A A 
 A B A A B B A A A 
AAA
2.
               A A A B B A 
                 A B A A B B A A A 
             A B A A B B A A A 
           A B A A B B A A A
     A B A A B B A A A
   A B A A B B A A A 
 A B A A B B A A A 
AABBA
3.
             A A A B B A
                 A B A A B B A A A
             A B A A B B A A A 
           A B A A B B A A A 
     A B A A B B A A A 
   A B A A B B A A A
 A B A A B B A A A 
ABBA
4.
             A A A B B A 
                 A B A A B B A A A
           A B A A B B A A A 
         A B A A B B A A A
BBA
5.
             A A A B B A
                   A B A A B B A A A 
             A B A A B B A A A 
           A B A A B B A A A
BA
6.
      A A A B B A 
                A B A A B B A A A 
            A B A A B B A A A 
          A B A A B B A A A
    A B A A B B A A A 
  A B A A B B A A A 
A B A A B B A A A 
A

Algorytm wyszukiwania najdłuższego wspólnego podłańcucha

Wejście:

s1, s2 : łańcuchy tekstowe, w których szukamy najdłuższego wspólnego podłańcucha

Wyjście:

lmax : długość najdłuższego wspólnego podłańcucha. Jeśli lmax jest równe 0, to brak wspólnego podłańcucha. lmax ∈ N.
p1 : pozycja najdłuższego wspólnego podłańcucha w s1; p1 ∈ N.
p2 : pozycja najdłuższego wspólnego podłańcucha w s2; p2 ∈ N.

Elementy pomocnicze:

i : indeks znaków w łańcuchu s1; i ∈ N.
j : indeks znaków w łańcuchu s2; j ∈ N.
m : długość łańcucha s1; m ∈ N.
n : długość łańcucha s2; n ∈ N.
lm : liczba znaków w podłańcuchu; lm ∈ N.

Lista kroków:

K01: m ← |s1| ; obliczamy długość łańcucha s1
K02: n ← |s2| ; obliczamy długość łańcucha s2
K03: s1wartownik1+s1+wartownik1 ; dodajemy wartownika do s1
K04: s2wartownik2+s2+wartownik2 ; dodajemy innego wartownika do s2
K05: lmax ← 0 ; zerujemy długość podłańcucha
K06: Dla i = 1, 2, …, m:
     wykonuj kroki K07…K14
K07:   Dla j = 1, 2, …, n:
       wykonuj kroki K08…K14
K08:     Jeśli s1[i] ≠ s2[j], ; szukamy zgodnego znaku w s1 i s2
         to następny obieg pętli K07
K09:     lm ← 1 ; ustawiamy wstępną długość podłańcucha
K10:     Dopóki s1[i+lm = s2[j+lm]: ; rozszerzamy podciąg w prawo
         wykonuj lmlm + 1
K11:     Jeśli lmlmax, ; sprawdzamy, czy podłańcuch jest
         to następny obieg pętli K07 ; dłuższy od zapamiętanego
K12      lmaxlm ; jeśli tak, zapamiętujemy go
K13:     p1i - 1 ; pozycja skorygowana z uwagi na strażnika
K14:     p2j - 1 ; pozycja skorygowana z uwagi na strażnika
K15: Usuń wartowników z s1 i s2 ; przywracamy stan s1 i s2
K16: Zakończ z wynikiem lmax, p1, p2

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 generuje dwa losowe łańcuchy po 40 znaków zbudowane z liter A i B. Wyszukuje w nich najdłuższy wspólny podłańcuch i wypisuje go odpowiednio pozycjonując łańcuchy względem siebie i wyznaczonego podłańcucha. Jeśli łańcuchy nie posiadają wspólnego podłańcucha, wypisywane jest słowo BRAK.
Pascal
// Wyszukiwanie najdłuższego podłańcucha
// Data: 10.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s1, s2 : ansistring;
  i, j, p1, p2, lm, lmax : integer;

begin
  randomize;

// generujemy łańcuchy s1 i s2

  s1 := ''; s2 := '';
  for i := 1 to 40 do
  begin
    s1 := s1 + char(65 + random(2));
    s2 := s2 + char(65 + random(2));
  end;

// wypisujemy łańcuchy s1 i s2

  writeln('s1 = ', s1);
  writeln('s2 = ', s2);

// szukamy najdłuższego wspólnego podłańcucha

  s1 := '$' + s1 + '$'; // dodajemy wartowników do s1
  s2 := '#' + s2 + '#'; // dodajemy wartowników do s2

  lmax := 0;

  for i := 2 to 41 do
    for j := 2 to 41 do
      if s1[i] = s2[j] then
      begin
        lm := 1;
        while s1[i+lm] = s2[j+lm] do inc(lm);
        if lm > lmax then
        begin
          lmax  := lm; p1 := i - 1; p2 := j - 1;
        end;
      end;
  s1 := copy(s1,2,40); // usuwamy wartowników z s1
  s2 := copy(s2,2,40); // usuwamy wartowników z s2

// prezentujemy wyniki

  writeln;
  if lmax = 0 then writeln('BRAK')
  else
  begin
    repeat
      if p1 > p2 then
      begin
        s2 := ' ' + s2; inc(p2);
      end
      else if p2 > p1 then
      begin
        s1 := ' ' + s1; inc(p1);
      end;
    until p1 = p2;
    writeln(s1);
    for i := 1 to p1 - 1 do write(' ');
    writeln(copy(s1,p1,lmax),' : ',lmax);
    writeln(s2);
  end;
end.
C++
// Wyszukiwanie najdłuższego podłańcucha
// Data: 10.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  string s1, s2;
  int i, j, p1, p2, lm, lmax;

  srand(time(NULL));

// generujemy łańcuchy s1 i s2

  s1 = ""; s2 = "";
  for(i = 0; i < 40; i++)
  {
    s1 += 65 + rand() % 2;
    s2 += 65 + rand() % 2;
  }

// wypisujemy łańcuchy s1 i s2

  cout << "s1 = " << s1 << endl
       << "s2 = " << s2 << endl;

// szukamy najdłuższego wspólnego podłańcucha

  s1 = "$" + s1 + "$"; // dodajemy wartowników do s1
  s2 = "#" + s2 + "#"; // dodajemy wartowników do s2

  lmax = 0;

  for(i = 1; i <= 40; i++)
    for(j = 1; j <= 40; j++)
      if(s1[i] == s2[j])
      {
        lm = 1;
        while(s1[i+lm] == s2[j+lm]) lm++;
        if(lm > lmax)
        {
          lmax  = lm; p1 = i - 1; p2 = j - 1;
        }
      }
  s1 = s1.substr(1,40); // usuwamy wartowników z s1
  s2 = s2.substr(1,40); // usuwamy wartowników z s2

// prezentujemy wyniki

  cout << endl;
  if(lmax == 0) cout << "BRAK\n";
  else
  {
    do
    {
      if(p1 > p2)
      {
        s2 = " " + s2; p2++;
      }
      else if(p2 > p1)
      {
        s1 = " " + s1; p1++;
      }
    } while(p1 != p2);
    cout << s1 << endl;
    for(i = 0; i < p1; i++) cout << " ";
    cout << s1.substr(p1,lmax) << ": " << lmax
         << endl
         << s2 << endl;
  }
  return 0;
}
Basic
' Wyszukiwanie najdłuższego podłańcucha
' Data: 10.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s1, s2
Dim As Integer i, j, p1, p2, lm, lmax

Randomize

' generujemy łańcuchy s1 i s2

s1 = "": s2 = ""
For i = 1 To 40
  s1 += Chr(65 + Cint(Rnd))
  s2 += Chr(65 + Cint(Rnd))
Next

' wypisujemy łańcuchy s1 i s2

Print "s1 = ";s1
Print "s2 = ";s2

' szukamy najdłuższego wspólnego podłańcucha

s1 = "$" + s1 + "$" ' dodajemy wartowników do s1
s2 = "#" + s2 + "#" ' dodajemy wartowników do s2

lmax = 0

For i = 2 To 41
  For j = 2 To 41
    If Mid(s1,i,1) = Mid(s2,j,1) Then
      lm = 1
      While Mid(s1,i+lm,1) = Mid(s2,j+lm,1)
        lm += 1
      Wend
      If lm > lmax Then
        lmax  = lm
        p1 = i - 1
        p2 = j - 1
      End If
    End If
  Next
Next
s1 = Mid(s1,2,40) ' usuwamy wartowników z s1
s2 = Mid(s2,2,40) ' usuwamy wartowników z s2

' prezentujemy wyniki

Print
If lmax = 0 Then
  Print "BRAK"
Else
  Do
    If p1 > p2 Then
      s2 = " " + s2: p2 += 1
    Elseif p2 > p1 Then
      s1 = " " + s1: p1 += 1
    End If
  Loop Until p1 = p2
  Print s1
  For i = 1 To p1 - 1: Print " ";: Next
  Print Mid(s1,p1,lmax);": ";lmax
  Print s2
End If
End
Python (dodatek)
# Wyszukiwanie najdłuższego podłańcucha
# Data: 15.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random

# generujemy łańcuchy s1 i s2

s1,s2 = "",""
for i in range(40):
    s1 += chr(random.randrange(65,67))
    s2 += chr(random.randrange(65,67))

# wypisujemy łańcuchy s1 i s2

print("s1 = %s\ns2 = %s" % (s1,s2))

# szukamy najdłuższego wspólnego podłańcucha

s1 = "$"+s1+"$" # dodajemy wartowników do s1
s2 = "#"+s2+"#" # dodajemy wartowników do s2

lmax = 0

for i in range(1,41):
    for j in range(1,41):
        if s1[i] == s2[j]:
            lm = 1
            while s1[i+lm] == s2[j+lm]:
                lm += 1
            if lm > lmax:
                lmax  = lm
                p1,p2 = i-1,j-1
s1 = s1[1:40] # usuwamy wartowników z s1
s2 = s2[1:40] # usuwamy wartowników z s2

# prezentujemy wyniki

print()
if not lmax:
    print("BRAK")
else:
    while True:
        if p1 > p2:
            s2 = " " + s2
            p2 += 1
        elif p2 > p1:
            s1 = " " + s1
            p1 += 1
        if p1 == p2:
            break
    print(s1)
    for i in range(p1):
        print(" ", end="")
    print(s1[p1:p1+lmax],":",lmax)
    print(s2)
Wynik:
s1 = BBABABBABBBBABBAABAABBBAAAABABBAAAAABBBB
s2 = AAAABBBBBBBAAAABBBABBABBABBAAABAAABBBABB

BBABABBABBBBABBAABAABBBAAAABABBAAAAABBB
                    BBBAAAAB : 8
            AAAABBBBBBBAAAABBBABBABBABBAAABAAABBBAB

Wyszukiwanie najdłuższego wspólnego podłańcucha
(C)2020 mgr Jerzy Wałaszek


Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

Drugie rozwiązanie wykorzystuje programowanie dynamiczne, gdzie zapamiętujemy w osobnej tablicy długości pasujących podłańcuchów w obu łańcuchach s1s2. Dzięki temu klasa złożoności obliczeniowej algorytmu spada do O(m × n). Algorytm dynamiczny wymaga dodatkowej pamięci rozmiaru O(m × n) na zapamiętywanie długości podłańcuchów. Zasada działania jest następująca:

Oznaczmy przez L[i+1,j+1] największą długość (ang. length) wspólnego podłańcucha kończącego się na pozycjach s1[i] oraz s2[j]. Długość tę wyznaczamy z długości L[i,j] w następujący sposób:

Jeśli s1[i] ≠ s2[j], to L[i+1,j+1] ← 0
Jeśli s1[i] = s2[j], to L[i+1,j+1] ← 1+L[i,j]

Wynika z tego, iż długość wspólnego podłańcucha rośnie o 1, jeśli znaki na pozycjach i oraz j w obu łańcuchach są zgodne. W przeciwnym razie długość zeruje się. Wyliczone długości są zapamiętywane w tablicy L, dzięki czemu w kolejnych obiegach pętli nie musimy ich wyznaczać.

Algorytm dynamiczny wyszukiwania najdłuższego wspólnego podłańcucha

Wejście:

 s1, s2 : łańcuchy tekstowe, w których szukamy najdłuższego wspólnego podłańcucha

Wyjście:

lmax : długość najdłuższego wspólnego podłańcucha. Jeśli lmax jest równe 0, to brak wspólnego podłańcucha. lmax ∈ N.
p1 : pozycja najdłuższego wspólnego podłańcucha w s1; p1 ∈ N.
p2 : pozycja najdłuższego wspólnego podłańcucha w s2; p2∈ N.

Elementy pomocnicze:

i : indeks znaków w łańcuchu  s1; i ∈ N.
j : indeks znaków w łańcuchu s2; j ∈ N.
m : długość łańcucha s1; m ∈ N.
n : długość łańcucha s2; n ∈ N.
L : dwuwymiarowa tablica zapamiętująca kolejne długości podłańcuchów. Wymiary L przebiegają od 0 do m oraz od 0 do n; L ∈ N.

Lista kroków:

K01: m ← |s1| ; obliczamy długość łańcucha s1
K02: n ← |s2| ; obliczamy długość łańcucha s2
K03: Utwórz tablicę L[m+1,n+1]
K04: Dla i = 0,1,…,m: ; zerujemy pierwszą kolumnę tablicy L
     wykonuj L[i,0] ← 0
K05: Dla j = 0,1,…,n: ; zerujemy pierwszy wiersz tablicy L
     wykonuj L[0,j] ← 0
K06: lmax ← 0 ; zerujemy największą długość wspólnego podłańcucha
K07: Dla i = 0,1,…,m-1: ; przebiegamy przez kolejne znaki s1
     wykonuj kroki K08…K16
K08:   Dla j = 0,1,…,n-1: ; przebiegamy przez kolejne znaki s2
       wykonuj kroki K09…K16
K09:   Jeśli s1[i] = s2[j], ; sprawdzamy równość znaków w łańcuchach
       to idź do kroku K12
K10:   L[i+1,j+1] ← 0 ; znaki są różne, długość zerujemy
K11:   Następny obieg pętli K07
K12:   L[i+1,j+1] ← 1+L[i,j] ; obliczamy nową długość wspólnego podłańcucha
K13:   Jeśli L[i+1,j+1] ≤ lmax, ; sprawdzamy, czy jest to najdłuższy podłańcuch
       to następny obieg pętli K07
K14:   lmaxL[i+1,j+1] ; zapamiętujemy długość wspólnego podłańcucha
K15:   p1i-lmax+1 ; oraz jego pozycję w s1
K16    p2j-lmax+1 ; i w s2
K17: Zakończ z wynikiem lmax, p1, p2

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 generuje dwa losowe łańcuchy po 40 znaków zbudowane z liter A i B. Wyszukuje w nich najdłuższy wspólny podłańcuch i wypisuje go odpowiednio pozycjonując łańcuchy względem siebie i wyznaczonego podłańcucha. Jeśli łańcuchy nie posiadają wspólnego podłańcucha, wypisywane jest słowo BRAK.
Pascal
// Wyszukiwanie najdłuższego podłańcucha
// Data: 16.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s1, s2 : ansistring;
  i, j, p1, p2, lmax : integer;
  L : array [0..40, 0..40] of integer;

begin
  randomize;

// generujemy łańcuchy s1 i s2

  s1 := ''; s2 := '';
  for i := 1 to 40 do
  begin
    s1 := s1 + char(65+random(2));
    s2 := s2 + char(65+random(2));
  end;

// wypisujemy łańcuchy s1 i s2

  writeln('s1 = ',s1);
  writeln('s2 = ',s2);

// szukamy najdłuższego wspólnego podłańcucha

  for i := 0 to 40 do
  begin
    L[i,0] := 0;
    L[0,i] := 0;
  end;

  lmax := 0;

  for i := 1 to 40 do
    for j := 1 to 40 do
      if s1[i] <> s2[j] then L[i,j] := 0
      else
      begin
        L[i,j] := 1+L[i-1,j-1];
        if L[i,j] > lmax then
        begin
          lmax := L[i,j];
          p1   := i-lmax+1;
          p2   := j-lmax+1;
        end;
      end;

// prezentujemy wyniki

  writeln;
  if lmax = 0 then writeln('BRAK')
  else
  begin
    repeat
      if p1 > p2 then
      begin
        s2 := ' '+s2; inc(p2);
      end
      else if p2 > p1 then
      begin
        s1 := ' '+s1; inc(p1);
      end;
    until p1 = p2;
    writeln(s1);
    for i := 1 to p1-1 do write(' ');
    writeln(copy(s1,p1,lmax),' : ',lmax);
    writeln(s2);
  end;
end.
C++
// Wyszukiwanie najdłuższego podłańcucha
// Data: 16.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  string s1, s2;
  int i, j, p1, p2, lmax, L[41][41];

  srand(time(NULL));

// generujemy łańcuchy s1 i s2

  s1 = ""; s2 = "";
  for(i = 0; i < 40; i++)
  {
    s1 += 65 + rand() % 2;
    s2 += 65 + rand() % 2;
  }

// wypisujemy łańcuchy s1 i s2

  cout << "s1 = " << s1 << endl
       << "s2 = " << s2 << endl;

// szukamy najdłuższego wspólnego podłańcucha

  for(i = 0; i <= 40; i++)
    L[i][0] = L[0][i] = 0;
  lmax = 0;
  for(i = 0; i < 40; i++)
    for(j = 0; j < 40; j++)
      if(s1[i] != s2[j]) L[i+1][j+1] = 0;
      else
      {
        L[i+1][j+1] = 1+L[i][j];
        if(L[i+1][j+1] > lmax)
        {
          lmax = L[i+1][j+1];
          p1   = i-lmax+1;
          p2   = j-lmax+1;
        }
      }

// prezentujemy wyniki

  cout << endl;
  if(lmax == 0) cout << "BRAK\n";
  else
  {
    do
    {
      if(p1 > p2)
      {
        s2 = " " + s2;
        p2++;
      }
      else if(p2 > p1)
           {
             s1 = " " + s1;
             p1++;
           }
    } while(p1 != p2);
    cout << s1 << endl;
    for(i = 0; i < p1; i++)
      cout << " ";
    cout << s1.substr(p1,lmax) << " : " << lmax
         << endl
         << s2 << endl;
  }
  return 0;
}
Basic
' Wyszukiwanie najdłuższego podłańcucha
' Data: 16.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s1, s2
Dim As Integer i, j, p1, p2,_
               lmax, L(40,40)

Randomize

' generujemy łańcuchy s1 i s2

s1 = "": s2 = ""
For i = 1 To 40
  s1 += Chr(65 + Cint(Rnd))
  s2 += Chr(65 + Cint(Rnd))
Next

' wypisujemy łańcuchy s1 i s2

Print "s1 = ";s1
Print "s2 = ";s2

' szukamy najdłuższego wspólnego podłańcucha

For i = 0 To 40
  L(i,0) = 0
  L(0,i) = 0
Next

lmax = 0

For i = 1 To 40
  For j = 1 To 40
    If Mid(s1,i,1) <> Mid(s2,j,1) Then
      L(i,j) = 0
    Else
      L(i,j) = 1+L(i-1,j-1)
      If L(i,j) > lmax Then
        lmax = L(i,j)
        p1   = i-lmax+1
        p2   = j-lmax+1
      End If
    End If
  Next
Next
     
' prezentujemy wyniki

Print
If lmax = 0 Then
  Print "BRAK"
Else
  Do
    If p1 > p2 Then
      s2 = " "+s2: p2 += 1
    Elseif p2 > p1 Then
      s1 = " "+s1: p1 += 1
    End If
  Loop Until p1 = p2
  Print s1
  For i = 1 To p1-1
    Print " ";
  Next
  Print Mid(s1,p1,lmax);" : ";lmax
  Print s2
End If
End
Python (dodatek)
# Wyszukiwanie najdłuższego podłańcucha
# Data: 16.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random

# konstruujemy tablicę dwuwymiarową

L = []
for i in range(41):
    a = []
    for j in range(41):
        a.append(0)
    L.append(a)

# generujemy łańcuchy s1 i s2

s1 = ""
s2 = ""
for i in range(40):
    s1 += chr(random.randrange(65,67))
    s2 += chr(random.randrange(65,67))

# wypisujemy łańcuchy s1 i s2

print("s1 =",s1)
print("s2 =",s2)

# szukamy najdłuższego wspólnego podłańcucha

lmax = 0
for i in range(40):
    for j in range(40):
        if s1[i] != s2[j]:
            L[i+1][j+1] = 0
        else:
            L[i+1][j+1] = 1+L[i][j]
            if L[i+1][j+1] > lmax:
                lmax = L[i+1][j+1]
                p1 = i-lmax+1
                p2 = j-lmax+1

# prezentujemy wyniki

print()
if lmax == 0: print("BRAK")
else:
    while True:
        if p1 > p2:
            s2 = " " + s2
            p2 += 1
        elif p2 > p1:
            s1 = " " + s1
            p1 += 1
        else: break
    print(s1)
    for i in range(p1):
        print(" ", end="")
    print(s1[p1:p1+lmax],":",lmax)
    print(s2)
print()

Zwróć uwagę, iż w prezentowanym powyżej algorytmie stosujemy dwuwymiarową tablicę L[m × n]. Tymczasem w tablicy tej wykorzystywane są tylko dwa wiersze – i-ty oraz (i-1)-szy. Algorytm możemy tak zmodyfikować, aby wymiar tablicy spadł do L[2 × n]. Zmniejszy to zapotrzebowanie na pamięć do rozmiaru O(n), zamiast O(m × n).

Algorytm dynamiczny wyszukiwania najdłuższego wspólnego podłańcucha

Wejście:

s1, s2 – łańcuchy tekstowe, w których szukamy najdłuższego wspólnego podłańcucha

Wyjście:

lmax – długość najdłuższego wspólnego podłańcucha. Jeśli lmax jest równe 0, to brak wspólnego podłańcucha; lmax ∈ N.
p1 – pozycja najdłuższego wspólnego podłańcucha s1; p1 ∈ N.
p2 – pozycja najdłuższego wspólnego podłańcucha s2; p2 ∈ N.

Elementy pomocnicze:

i : indeks znaków w łańcuchu s1; i ∈ N.
j : indeks znaków w łańcuchu s2; j ∈ N.
m : długość łańcucha s1; m ∈ N.
: długość łańcucha s2; n ∈ N.
L : dwuwymiarowa tablica zapamiętująca kolejne długości podłańcuchów. Wymiary L przebiegają od 0 do 1 oraz od 0 do n; L ∈ N.

Lista kroków:

K01: m ← |s1| ; obliczamy długość łańcucha s1
K02: n ← |s2| ; obliczamy długość łańcucha s2
K03: Twórz tablicę L[2,n+1]
K04: Dla j = 0,1,…,n: ; zerujemy pierwszy wiersz tablicy L
     wykonuj L[0,j] ← 0
K05: lmax ← 0 ; zerujemy największą długość wspólnego podłańcucha
K06: Dla i = 0,1,…,m-1: ; przebiegamy przez kolejne znaki s1
     wykonuj kroki K07…K16
K07:   Dla j = 0,1,…,n-1: ; przebiegamy przez kolejne znaki s2
       wykonuj kroki K08…K15
K08:     Jeśli s1[i] = s2[j], ; sprawdzamy równość znaków
         to idź do kroku K11
K09:     L[1,j+1] ← 0 ; znaki są różne, długość zerujemy
K10:     Następny obieg pętli K06
K11:     L[1,j+1] ← 1+L[0,j] ; obliczamy nową długość wspólnego podłańcucha
K12:     Jeśli L[1,j+1] ≤ lmax, ; sprawdzamy, czy jest to najdłuższy podłańcuch
         to następny obieg pętli K06
K13:     lmaxL[1,j+1] ; zapamiętujemy długość wspólnego podłańcucha
K14:     p1i-lmax+1   ; oraz jego pozycję w s1
K15:     p2j-lmax+1   ; i w s2
K16:   Dla j = 0,1,…,n:  ; przepisujemy wiersz 1 do wiersza 0 tablicy L
       wykonuj L[0,j] ← L[1,j]
K17: Zakończ z wynikiem lmax,p1,p2

Zmodyfikowanie przykładowych programów wg nowego algorytmu pozostawiam czytelnikowi jako proste ćwiczenie w programowaniu. A może wymyślisz sposób przełączania wierszy tablicy L bez konieczności ich przepisywania - zastanów się nad dwoma dodatkowymi zmiennymi indeksującymi wiersze tej tablicy.


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.