Algorytmy i Struktury Danych - Najdłuższy wspólny podłańcuch

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^2 \cdot n)}\), 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₁ = AAABBA
s₂ = ABAABBAAA

Lp.	Kolejne dopasowania s₂ do s₁	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} \in \mathbb{N}}\).
\(p_1\) : pozycja najdłuższego wspólnego podłańcucha w \(s_1\); \({p_1 \in \mathbb{N}}\).
\(p_2\) : pozycja najdłuższego wspólnego podłańcucha w \(s_2\); \({p_2 \in \mathbb{N}}\).

Elementy pomocnicze:

\(i\) : indeks znaków w łańcuchu \(s_1\); \({i \in \mathbb{N}}\).
\(j\) : indeks znaków w łańcuchu \(s_2\); \({j \in \mathbb{N}}\).
\(m\) : długość łańcucha \(s_1\); \({m \in \mathbb{N}}\).
\(n\) : długość łańcucha \(s_2\); \({n \in \mathbb{N}}\).
\(l_m\) : liczba znaków w podłańcuchu; \({l_m \in \mathbb{N}}\).

Lista kroków:

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

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

p1,p2 = 0, 0
# 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

JavaScript

<html>
  <head>
    <title>
      Najdłuższy
      wspólny
      podłańcuch
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          Wyszukiwanie najdłuższego
          <br>
          wspólnego podłańcucha
          </b><br/>
          &nbsp;&nbsp;(C)2026 mgr
          Jerzy	Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main();">
          <hr>
          <b>Wynik:</b>
          <div
          align="center"
          class="small">
            <table
            border="0"
            cellpadding="0"
            style="border-collapse:
                   collapse">
              <tr>
                <td
                valign="top"
                style="text-align:
                      left">
<pre id="out">.</pre>
                </td>
              </tr>
            </table>
          </div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Wyszukiwanie najdłuższego
// podłańcucha
// Data: 10.07.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main()
{
  var s1,s2,ss,i,j,ps1,ps2,
      pmax1,pmax2,lm,lmax,tx;

  // generujemy
  // łańcuchy s1 i s2

  s1 = "";
  s2 = "";
  for(i = 0; i < 40; i++)
  {
    s1 += String.fromCharCode(
          65 + Math.floor(
          Math.random() * 2));
    s2 += String.fromCharCode(
          65 + Math.floor(
          Math.random() * 2));
  }

  // wypisujemy
  // łańcuchy s1 i s2

  tx = "s<sub>1</sub> = " +
       s1 + "<br/>s<sub>2</sub> = " +
       s2 + "<br/>";

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

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

  lmax = 0;

  for(i = 1; i <= 40; i++)
    for(j = 1; j <= 40; j++)
      if(s1.charAt(i) ==
         s2.charAt(j))
      {
        lm = 1;
        ps1 = i;
        ps2 = j;
        while(s1.charAt(ps1 + lm) ==
              s2.charAt(ps2 + lm))
          lm++;
        while(s1.charAt(ps1 - 1) ==
              s2.charAt(ps2 - 1))
        {
          lm++;
          ps1--;
          ps2--;
        }
        if(lm > lmax)
        {
          lmax = lm;
          pmax1 = ps1 - 1;
          pmax2 = ps2 - 1;
        }
      }
  // usuwamy strażników z s1
  s1 = s1.substr(1, 40);
  // usuwamy strażników z s2
  s2 = s2.substr(1, 40);

  // prezentujemy wyniki
  tx += "<br/>";
  if(lmax == 0)
    tx += "<b>BRAK</b>";
  else
  {
    ss = s1.substr(pmax1, lmax);
    do
    {
      if(pmax1 > pmax2)
      {
        s2 = "&nbsp;" + s2;
        pmax2++;
      }
      else if(pmax2 > pmax1)
      {
        s1 = "&nbsp;" + s1;
        pmax1++;
      }
    } while(pmax1 != pmax2);
    tx += s1 + "<br/>";
    for(i = 0; i < pmax1; i++)
      tx += "&nbsp;";
    tx += ss + " : " + lmax +
          "<br/>" + s2;
  }
  document.getElementById("out")
  .innerHTML = "<b>" + tx + "</b>";
}

</script>

  </body>
</html>

do podrozdziału do strony

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 \cdot n)}\). Algorytm dynamiczny wymaga dodatkowej pamięci rozmiaru \({O(m \cdot 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₁[i] ≠ s₂[j], to L[i+1, j+1] ← 0
Jeśli s₁[i] = s₂[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:

Elementy pomocnicze:

\(i\) : indeks znaków w łańcuchu \(s_1\); \({i \in \mathbb{N}}\).
\(j\) : indeks znaków w łańcuchu \(s_2\); \({j \in \mathbb{N}}\).
\(m\) : długość łańcucha \(s_1\); \({m \in \mathbb{N}}\).
\(n\) : długość łańcucha \(s_2\); \({n \in \mathbb{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 \in \mathbb{N}}\).

Lista kroków:

K01: m ← |s₁| ; obliczamy długość łańcucha s₁K02: n ← |s₂| ; obliczamy długość łańcucha s₂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: l_max ← 0 ; zerujemy największą długość wspólnego podłańcucha
K07: Dla i = 0, 1, …, m-1: ; przebiegamy przez kolejne znaki s₁
     wykonuj kroki K08…K16
K08:   Dla j = 0, 1, …, n-1: ; przebiegamy przez kolejne znaki s₂
       wykonuj kroki K09…K16
K09:   Jeśli s₁[i] = s₂[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] ≤ l_max, ; sprawdzamy, czy jest to najdłuższy podłańcuch
       to następny obieg pętli K07
K14:   l_max ← L[i+1, j+1] ; zapamiętujemy długość wspólnego podłańcucha
K15:   p₁ ← i-l_max+1 ; oraz jego pozycję w s₁K16    p₂ ← j-l_max+1 ; i w s₂K17: Zakończ z wynikiem l_max, p₁, p₂

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.

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

N = 40 # Długość łańcuchów

p1, p2 = 0, 0
# konstruujemy tablicę dwuwymiarową
t_l = [[0 for j in range(N+1)] for i in range(41)]
# generujemy łańcuchy s1 i s2
s1 = ""
s2 = ""
for i in range(N):
    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]:
            t_l[i+1][j+1] = 0
        else:
            t_l[i+1][j+1] = 1+t_l[i][j]
            if t_l[i+1][j+1] > lmax:
                lmax = t_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 \times n]}\). Tymczasem w tablicy tej wykorzystywane są tylko dwa wiersze – \({i{-}\text{ty}}\) oraz \({(i-1){-}\text{szy}}\). Algorytm możemy tak zmodyfikować, aby wymiar tablicy spadł do \({L[2 \times n]}\). Zmniejszy to zapotrzebowanie na pamięć do rozmiaru \({O(n)}\), zamiast \({O(m \cdot n)}\).

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} \in \mathbb{N}}\).
\(p_1\) – pozycja najdłuższego wspólnego podłańcucha w \(s_1\); \({p_1 \in \mathbb{N}}\).
\(p_2\) – pozycja najdłuższego wspólnego podłańcucha w \(s_2\); \({p_2 \in \mathbb{N}}\).

Elementy pomocnicze:

\(i\) : indeks znaków w łańcuchu \(s_1\); \({i \in \mathbb{N}}\).
\(j\) : indeks znaków w łańcuchu \(s_2\); \({j \in \mathbb{N}}\).
\(m\) : długość łańcucha \(s_1\); \({m \in \mathbb{N}}\).
\(n\) : długość łańcucha \(s_2\); \({n \in \mathbb{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 \in \mathbb{N}}\).

Lista kroków:

K01: m ← |s₁| ; obliczamy długość łańcucha s₁K02: n ← |s₂| ; obliczamy długość łańcucha s₂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: l_max ← 0 ; zerujemy największą długość wspólnego podłańcucha
K06: Dla i = 0, 1, …, m-1: ; przebiegamy przez kolejne znaki s₁
     wykonuj kroki K07…K16
K07:   Dla j = 0, 1, …, n-1: ; przebiegamy przez kolejne znaki s₂
       wykonuj kroki K08…K15
K08:     Jeśli s₁[i] = s₂[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] ≤ l_max, ; sprawdzamy, czy jest to najdłuższy podłańcuch
         to następny obieg pętli K06
K13:     l_max ← L[1, j+1] ; zapamiętujemy długość wspólnego podłańcucha
K14:     p₁ ← i-l_max+1 ; oraz jego pozycję w s₁K15:     p₂ ← j-l_max+1 ; i w s₂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 l_max, p₁, p₂

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.

do podrozdziału do strony

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.

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

Problem

Rozwiązanie nr 1

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków: