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


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Wyszukiwanie max lub min
  Rozwiązanie 1
Rozwiązanie 2

 

Problem

Dla danych, niepustych łańcuchów tekstowych s1 i s2 znaleźć 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ńcuchu s1 i s2. Problem wyszukiwania wspólnych sekwencji symboli jest szeroko wykorzystywany w badaniach genetycznych łańcuchów DNA.

 

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(m2n), gdzie m jest długością łańcucha s1, a 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: s1 ← wartownik1 + s1 + wartownik1 ; dodajemy wartownika do s1
K04: s2 ← wartownik2 + s2 + wartownik2 ; dodajemy innego wartownika do s2
K05: lmax ← 0 ; zerujemy długość podłańcucha
K06: Dla i = 1,2,...,m wykonuj K07...K14  
K07:     Dla j = 1,2,...,n wykonuj K08...K14  
K08:         Jeśli s1[i] ≠ s2[j], to następny obieg pętli K07 ; szukamy zgodnego znaku w s1 i s2
K09:         lm ← 1 ; ustawiamy wstępną długość podłańcucha
K10:         Dopóki s1[i + lm] = s2[j + lm], wykonuj lmlm + 1 ; rozszerzamy podciąg w prawo
K11:         Jeśli lmlmax, to następny obieg pętli K07 ; sprawdzamy, czy podłańcuch jest 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  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie najdłuższego podłańcucha
// Data: 10.07.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie najdłuższego podłańcucha
// Data: 10.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

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

  srand((unsigned)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;
}
Free Basic
' Wyszukiwanie najdłuższego podłańcucha
' Data: 10.07.2008
' (C)2012 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
Wynik
s1 = AAAAAABBAAABBBBBAABBAAAAABBBABAABBBBABBA
s2 = AAAABBBBBABBBAAAAAAABAABBAABBAAABBBAABBA

                     AAAAAABBAAABBBBBAABBAAAAABBBABAABBBBABBA
                         AABBAAABBB : 10
AAAABBBBBABBBAAAAAAABAABBAABBAAABBBAABBA

 

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


...

 

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 s1 i s2. Dzięki temu klasa złożoności obliczeniowej algorytmu spada do O(mn). Algorytm dynamiczny wymaga dodatkowej pamięci rozmiaru O(mn) 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: Dla i = 0,1,...,m: L[i,0] ← 0 ; zerujemy pierwszą kolumnę tablicy L
K04: Dla j = 0,1,...,n: L[0,j] ← 0 ; zerujemy pierwszy wiersz tablicy L
K05: lmax ← 0 ; zerujemy największą długość wspólnego podłańcucha
K06: Dla i = 0,1,...,m - 1: wykonuj K07...K15 ; przebiegamy przez kolejne znaki s1
K07:     Dla j = 0,1,...,n - 1: wykonuj K08...K15 ; przebiegamy przez kolejne znaki s2
K08:         Jeśli s1[i] = s2[j], idź do K11 ; sprawdzamy równość znaków s1[i] z s2[j]
K09:         L[i+1,j+1] ← 0 ; znaki są różne, długość zerujemy
K10:         Następny obieg pętli K06  
K11:         L[i+1,j+1] ← 1 + L[i,j] ; obliczamy nową długość wspólnego podłańcucha
K12:         Jeśli L[i+1,j+1] ≤ lmax, to idź do K10 ; sprawdzamy, czy jest to najdłuższy podłańcuch
K13:         lmax ← L[i+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: Zakończ z wynikiem lmax,p1,p2  


Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie najdłuższego podłańcucha
// Data: 16.07.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie najdłuższego podłańcucha
// Data: 16.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

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

  srand((unsigned)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;
}
Free Basic
' Wyszukiwanie najdłuższego podłańcucha
' Data: 16.07.2008
' (C)2012 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

 

Zwróć uwagę, iż w prezentowanym powyżej algorytmie stosujemy dwuwymiarową tablicę L[m × n]. Tymczasem w tablicy tej wykorzystywane są naraz 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(mn).

 

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 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: Dla j = 0,1,...,n: L[0,j] ← 0 ; zerujemy pierwszy wiersz tablicy L
K04: lmax ← 0 ; zerujemy największą długość wspólnego podłańcucha
K05: Dla i = 0,1,...,m - 1: wykonuj K06...K15 ; przebiegamy przez kolejne znaki s1
K06:     Dla j = 0,1,...,n - 1: wykonuj K07...K14 ; przebiegamy przez kolejne znaki s2
K07:         Jeśli s1[i] = s2[j], idź do K10 ; sprawdzamy równość znaków s1[i] z s2[j]
K08:         L[1,j+1] ← 0 ; znaki są różne, długość zerujemy
K09:         Następny obieg pętli K05  
K10:         L[1,j+1] ← 1 + L[0,j] ; obliczamy nową długość wspólnego podłańcucha
K11:         Jeśli L[1,j+1] ≤ lmax, to idź do K09 ; sprawdzamy, czy jest to najdłuższy podłańcuch
K12:         lmax ← L[1,j+1] ; zapamiętujemy długość wspólnego podłańcucha
K13:         p1i - lmax + 1 ; oraz jego pozycję w s1
K14         p2j - lmax + 1 ; i w s2
K15:     Dla j = 0,1,...,n: L[0,j] ← L[1,j] ; przepisujemy wiersz 1 do wiersza 0 tablicy L
K16: 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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.