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

©2020 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 s 1 i s 2 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 s 1 i s 2. 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 s 1 do fragmentów łańcucha s 2 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 s 1. Wyszukujemy w s 2 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 s 1 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 ( m 2n  ), gdzie m  jest długością łańcucha s 1, a n  jest długością łańcucha s 2.

Przykład:

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

s 1 = AAABBA
s 2 = ABAABBAAA

Lp. Kolejne dopasowania s 2 do s 1 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:

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

Wyjście:

l max  – długość najdłuższego wspólnego podłańcucha. Jeśli l max  jest równe 0, to brak wspólnego podłańcucha. l max  ∈ N.
p 1 – pozycja najdłuższego wspólnego podłańcucha w s 1, p 1  ∈ N.
p 2 – pozycja najdłuższego wspólnego podłańcucha w s 2, p 2  ∈ N.

Zmienne pomocnicze:

i  –  indeks znaków w łańcuchu s 1, i  ∈ N
j  – indeks znaków w łańcuchu s 2, j  ∈ N
m  – długość łańcucha s 1, m  ∈ N
n  – długość łańcucha s 2, n  ∈ N
l m  – liczba znaków w podłańcuchu, l m  ∈ N

Lista kroków:

K01: m  ← | s 1 | obliczamy długość łańcucha s 1
K02: n  ← | s 2 | obliczamy długość łańcucha s 2
K03: s 1 ← wartownik 1 + s 1 + wartownik 1 dodajemy wartownika do s 1
K04: s 2 ← wartownik 2 + s 2 + wartownik 2 dodajemy innego wartownika do s 2
K05: l max  ← 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 s 1 [ i  ] ≠ s 2 [ j  ],
        to następny obieg pętli K07
szukamy zgodnego znaku w s 1 i s 2
K09:         l m  ← 1 ustawiamy wstępną długość podłańcucha
K10:         Dopóki s 1 [ i + l m  ] = s 2 [ j + l m  ],
        wykonuj l m  ← l m  + 1
rozszerzamy podciąg w prawo
K11:         Jeśli l m  ≤ l max,
        to następny obieg pętli K07
sprawdzamy, czy podłańcuch jest dłuższy od zapamiętanego
K12         l max  ← l m jeśli tak, zapamiętujemy go
K13:         p 1i  - 1 pozycja skorygowana z uwagi na strażnika
K14:         p 2j  - 1 pozycja skorygowana z uwagi na strażnika
K15: Usuń wartowników z s 1 i s 2 przywracamy stan s 1 i s 2
K16: Zakończ z wynikiem l max, p 1, p 2  

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 <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;
}
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
Wynik:
s1 = AAAAAABBAAABBBBBAABBAAAAABBBABAABBBBABBA
s2 = AAAABBBBBABBBAAAAAAABAABBAABBAAABBBAABBA

                     AAAAAABBAAABBBBBAABBAAAAABBBABAABBBBABBA
                         AABBAAABBB : 10
AAAABBBBBABBBAAAAAAABAABBAABBAAABBBAABBA
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 s 1 i s 2. 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 s 1 [ i  ] oraz s 2 [ j  ]. Długość tę wyznaczamy z długości L [ i, j  ] w następujący sposób:

Jeśli s 1 [ i  ] ≠ s 2 [ j  ], to L [ i + 1, j + 1 ] ← 0
Jeśli s 1 [ i  ] = s 2 [ 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:

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

Wyjście:

l max  – długość najdłuższego wspólnego podłańcucha. Jeśli l max  jest równe 0, to brak wspólnego podłańcucha. l max  ∈ N.
p 1 – pozycja najdłuższego wspólnego podłańcucha w s 1, p 1  ∈ N.
p 2 – pozycja najdłuższego wspólnego podłańcucha w s 2, p 2  ∈ N.

Zmienne pomocnicze:

i  –  indeks znaków w łańcuchu s 1, i  ∈ N.
j  – indeks znaków w łańcuchu s 2, j  ∈ N.
m  – długość łańcucha s 1, m  ∈ N
n  – długość łańcucha s 2, 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  ← | s 1 | obliczamy długość łańcucha s 1
K02: n  ← | s 2 | obliczamy długość łańcucha s 2
K03: Dla i  = 0, 1, ..., m :
wykonuj L [ i, 0 ] ← 0
zerujemy pierwszą kolumnę tablicy L
K04: Dla j  = 0, 1, ..., n :
wykonuj L [ 0, j  ] ← 0
zerujemy pierwszy wiersz tablicy L
K05: l max  ← 0 zerujemy największą długość wspólnego podłańcucha
K06: Dla i  = 0, 1, ..., m  - 1:
wykonuj kroki K07...K15
przebiegamy przez kolejne znaki s 1
K07:     Dla j  = 0, 1, ..., n - 1:
    wykonuj kroki K08...K15
przebiegamy przez kolejne znaki s 2
K08:         Jeśli s 1 [ i  ] = s 2 [ j  ],
        to idź do kroku K11
sprawdzamy równość znaków s 1 [ i ] z s 2 [ 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 ] ≤ l max,
        to idź do kroku K10
sprawdzamy, czy jest to najdłuższy podłańcuch
K13:         l max  ← L [ i + 1, j + 1 ] zapamiętujemy długość wspólnego podłańcucha
K14:         p 1i  - l max  + 1 oraz jego pozycję w s 1
K15         p 2j  - l max  + 1 i w s 2
K16: Zakończ z wynikiem l max, p 1, p 2  

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 <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;
}
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

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:

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

Wyjście:

l max  – długość najdłuższego wspólnego podłańcucha. Jeśli l max  jest równe 0, to brak wspólnego podłańcucha. l max  ∈ N.
p 1 – pozycja najdłuższego wspólnego podłańcucha w s 1, p 1  ∈ N.
p 2 – pozycja najdłuższego wspólnego podłańcucha w s 2, p 2  ∈ N.

Zmienne pomocnicze:

i  –  indeks znaków w łańcuchu s 1, i  ∈ N.
j  – indeks znaków w łańcuchu s 2, j  ∈ N.
m  – długość łańcucha s 1, m  ∈ N
n  – długość łańcucha s 2, 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  ← | s 1 | obliczamy długość łańcucha s 1
K02: n  ← | s 2 | obliczamy długość łańcucha s 2
K03: Dla j  = 0, 1, ..., n :
wykonuj L [ 0, j  ] ← 0
zerujemy pierwszy wiersz tablicy L
K04: l max  ← 0 zerujemy największą długość wspólnego podłańcucha
K05: Dla i  = 0, 1, ..., m  - 1:
wykonuj kroki K06...K15
przebiegamy przez kolejne znaki s 1
K06:     Dla j  = 0, 1, ..., n - 1:
    wykonuj kroki K07...K14
przebiegamy przez kolejne znaki s 2
K07:         Jeśli s 1 [ i  ] = s 2 [ j  ],
        to idź do kroku K10
sprawdzamy równość znaków s 1 [ i ] z s 2 [ 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 ] ≤ l max,
        to idź do kroku K09
sprawdzamy, czy jest to najdłuższy podłańcuch
K12:         l max  ← L [ 1, j + 1 ] zapamiętujemy długość wspólnego podłańcucha
K13:         p 1i  - l max  + 1 oraz jego pozycję w s 1
K14         p 2j  - l max  + 1 i w s 2
K15:     Dla j  = 0, 1, ..., n :
    wykonuj L [ 0, j ] ← L [ 1, j ]
przepisujemy wiersz 1 do wiersza 0 tablicy L
K16: Zakończ z wynikiem l max, p 1, p 2  

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
©2020 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.