Algorytmy i Struktury Danych

SPIS TREŚCI

Tematy pomocnicze

Podrozdziały

Rozwiązanie 1
Rozwiązanie 2

Problem

W łańcuchu s należy znaleźć wszystkie palindromy o długości większej od 1.

Przez palindrom (ang. palindrome) rozumiemy łańcuch znakowy s, który czyta się tak samo w obu kierunkach.

Przykład:

ABBCBBA – jest palindromem
ABBCABA – nie jest palindromem

Palindromy pojawiają się w genetyce (łańcuchy DNA, RNA), w tekstach, muzyce, matematyce, geometrii, fizyce itd. Stąd duże zainteresowanie informatyków w efektywnych algorytmach ich znajdowania. W badaniach genetycznych często szuka się tzw. przybliżonych palindromów ( ang. aproximate palindromes), tzn. palindromów, w których do k-znaków może być błędnych, czyli nie pasujących do dokładnego palindromu (ang. exact palindrome). Takie palindromy występują w łańcuchach DNA, w których wystąpiły różnego rodzaju błędy genetyczne. Problemem palindromów przybliżonych nie zajmujemy się w tym artykule.

Wprowadźmy symbol s^R, który oznacza łańcuch znakowy o odwróconej kolejności znaków w stosunku do łańcucha s.

Przykład:

s = ABCD
s^R = DCBA

Łańcuch s jest palindromem, jeśli da się rozłożyć na dwa podłańcuchy w i w^R wg poniższego schematu:

s = ww^R – palindrom parzysty (ang. even palindrome), lub
s = wXw^R – palindrom nieparzysty (ang. odd palindrome), gdzie X jest dowolnym symbolem alfabetu.

Przykład:

ABCDDCBA – palindrom parzysty → ABCD+DCBA
ABCDADCBA – palindrom nieparzysty → ABCD+A+DCBA

Zauważ, iż zgodnie z tą definicją palindromem jest każdy łańcuch pusty – rozkłada się na dwa puste podłańcuchy – oraz każdy łańcuch jednoliterowy – rozkłada się na znak X i dwa puste podłańcuchy. Ponieważ są to przypadki trywialne, w zadaniu wprowadzono zastrzeżenie, iż wyszukiwane palindromy muszą być co najmniej dwuznakowe.

Pierwszy algorytm wyszukiwania palindromów jest algorytmem naiwnym. Rozkłada on dany łańcuch znakowy s na wszystkie możliwe podłańcuchy p o długości nie mniejszej niż 2 znaki i sprawdza następnie, czy dadzą się przedstawić w postaci ww^R lub wXw^R. Sprawdzenie polega na porównywaniu znaków od początku i od końca podłańcucha. W tym celu wykorzystuje się dwa indeksy. Jeden z nich ustawia się na pierwszym znaku podłańcucha p, a drugi na ostatnim. Następnie porównujemy wskazywane przez te indeksy znaki podłańcucha p. Jeśli znaki są różne, to podłańcuch p nie jest palindromem. Jeśli porównywane znaki są równe, to indeksy przesuwamy – lewy w prawo, a prawy w lewo. Jeśli indeksy się miną, to zachodzi jedna z dwóch równości:

p = ww^R,  lub p = wXw^R

W takim przypadku p jest palindromem. Wyszukanie wszystkich palindromów zawartych w łańcuchu s proponowaną metodą posiada sześcienną klasę złożoności obliczeniowej O(n³), gdzie n jest długością łańcucha s.

Algorytm naiwny wyszukiwania palindromów

Wejście:

s : łańcuch tekstowy.

Wyjście:

Wszystkie palindromy zawarte w łańcuchu s.

Elementy pomocnicze:

i, j : indeksy znaków w łańcuchu s; i, j ∈ N.
n : długość łańcucha s; n ∈ N.
i_P : prawy indeks; i_P ∈ N.
i_L : lewy indeks; i_L ∈ N.

Lista kroków:

K01: n ← |s|
K02: Dla i = 0, 1, …, n-2: ; przeglądamy łańcuch s
     wykonuj kroki K03…K10
K03:   Dla j = i+2, i+3, …, n-1:
       wykonuj kroki K04…K10
K04:   i_L ← i ; lewy indeks na pierwszym znaku podsłowa
K05:   i_P ← j-1 ; prawy indeks na ostatnim znaku podsłowa
K06:   Dopóki i_L < i_P, ; sprawdzamy, czy podsłowo jest palindromem
       wykonuj kroki K07…K09
K07:     Jeśli s[i_L] ≠ s[i_P], 
         to następny obieg pętli K03
K08:     i_L ← i_L+1 ; lewy indeks przesuwamy w prawo
K09:     i_P ← i_P-1 ; a prawy w lewo
K10:   Pisz s[i:j] ; wyprowadzamy znaleziony palindrom
K11: 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 generuje 40 znakowy łańcuch zbudowany ze znaków {A, B, C, D}, wyszukuje w nim wszystkie palindromy i wypisuje je z odpowiednim przesunięciem.

Pascal

// Wyszukiwanie palindromów
// Data: 9.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 40; // długość łańcucha s

var
  s : ansistring;
  i, j, k, iP, iL : integer;
  t : boolean;

begin

  // generujemy łańcuch s
  randomize;
  s := '';
  for i := 1 to N do
    s := s+chr(65+random(4));

  // wypisujemy łańcuch s
  writeln(s);

  // szukamy palindromów
  for i := 1 to N-1 do
    for j := i+2 to N+1 do
    begin
      iL := i; iP := j-1; t := true;
      while iL < iP do
      begin
        if s[iL] <> s[iP] then
        begin
          t := false; break;
        end;
        inc(iL); dec(iP);
      end;
      if t then
      begin
        for k := 2 to i do write(' ');
        writeln(copy(s, i, j-i));
      end;
    end;
  writeln;
end.

C++

// Wyszukiwanie palindromów
// Data: 9.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

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

using namespace std;

const int N = 40; // długość łańcucha s

int main()
{
  string s;
  int i, j, k, iP, iL;
  bool t;

  // generujemy łańcuch s
  srand(time(NULL));
  s = "";
  for(i = 0; i < N; i++)
    s += char(65+rand()%4);

  // wypisujemy łańcuch s
  cout << s << endl;

  // szukamy palindromów
  for(i = 0; i < N-1; i++)
    for(j = i+2; j <= N; j++)
    {
      iL = i; iP = j-1; t = true;
      while(iL < iP)
        if(s[iL++] != s[iP--])
        {
          t = false; break;
        }
      if(t)
      {
        for(k = 0; k < i; k++)
          cout << " ";
        cout << s.substr(i, j-i) << endl;
      }
    }
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie palindromów
' Data: 9.08.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 40 ' długość łańcucha s

Dim As String s
Dim As Integer i, j, k, iP, iL, t

' generujemy łańcuch s
Randomize
s = ""
For i = 1 To N
  s += Chr(65+Cint(Rnd*3))
Next

' wypisujemy łańcuch s
Print s

' szukamy palindromów
For i = 1 To N-1
  For j = i+2 To N+1
    iL = i: iP = j-1: t = 1
    While iL < iP
      If Mid(s, iL, 1) <> Mid(s, iP, 1) Then
        t = 0: Exit While
      End If
      iL += 1: iP -= 1
    Wend
    If t = 1 Then
      For k = 2 To i
        Print " ";
      Next
      Print Mid(s, i, j-i)
    End If
  Next
Next
Print
End

Python (dodatek)

# Wyszukiwanie palindromów
# Data: 21.03.2024
# (C)2020 mgr Jerzy Wałaszek
#---------------------------

import random

N = 40 # długość łańcucha s

# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(65, 69))
# wypisujemy łańcuch s
print(s)
# szukamy palindromów
for i in range(N-1):
    for j in range(i+2, N+1):
        i_l, i_p, t = i, j-1, True
        while i_l < i_p:
            if s[i_l] != s[i_p]:
                t = False
                break
            i_l += 1
            i_p -= 1
        if t:
            for k in range(i):
                print(" ", end="")
            print(s[i:j])
print()

Wynik:

DCCAACBDADCAADDBDADBCDCCBCBAACBBADBCDDAD
 CC
  CAAC
   AA
       DAD
           AA
             DD
              DBD
               BDADB
                DAD
                    CDC
                      CC
                       CBC
                        BCB
                           AA
                              BB
                                    DD
                                     DAD

do podrozdziału do strony

Drugie podejście do rozwiązania problemu wyszukiwania wszystkich palindromów w łańcuchu znakowym s opiera się na własnościach palindromów. Przedstawiony tutaj algorytm został opracowany w 1975 przez Glenna Manachera z Computer Center and Department of Information Engineering, University of Illinois, Chicago, IL. Do opisu algorytmu Manachera wprowadzimy kilka nowych pojęć.

Niech p_P będzie palindromem parzystym o postaci p_P = ww^R, gdzie w jest niepustym podłańcuchem.
Niech p_N będzie palindromem nieparzystym o postaci p_N = wXw^R.

Promieniem r_P palindromu p będziemy nazywali długość podsłowa w, czyli r_P = |w|

Palindrom parzysty p_P posiada zawsze długość |p_P| = 2r_P. Palindrom nieparzysty p_N posiada zawsze długość |p_N| = 2r_P+1.

Środkiem palindromu p jest pozycja i_s = r_P – jest to pozycja pierwszego znaku za słowem w (można również definiować środek palindromu jako pozycję ostatniego znaku podsłowa w, lecz sądzę, iż nasz sposób jest lepszy, gdyż nie wymaga wprowadzania żadnych zmian dla palindromów nieparzystych) Dla palindromu parzystego środek wypadnie na pierwszym znaku w^R natomiast dla palindromu nieparzystego środek wypadnie na znaku X:

p_P[r_P] = w^R[0] 
p_N[r_P] = X

Algorytm Manachera nie wyznacza wszystkich palindromów, jak robi to algorytm naiwny, lecz maksymalne palindromy, których środki występują na kolejnych pozycjach znakowych przeszukiwanego łańcucha s. Dzięki takiemu podejściu redukujemy złożoność obliczeniową fazy przeszukiwania łańcucha s. Mając maksymalny palindrom możemy bez problemów wyznaczyć zawarte w nim podpalindromy. Wykorzystujemy tutaj własność symetrii palindromu:

Przykład:

r_P	palindrom parzysty	palindrom nieparzysty
4	ABCDDCBA	ABCDADCBA
3	BCDDCB	BCDADCB
2	CDDC	CDADC
1	DD	DAD

Dla danego łańcucha s algorytm Manachera tworzy tablicę dwuwymiarową R:

R[0, …] – promienie palindromów parzystych
R[1, …] – promienie palindromów nieparzystych

Indeksy tych tablic określają kolejne pozycje znakowe w łańcuchu s, natomiast elementy tablic zawierają maksymalne promienie palindromów o środkach na danej pozycji znakowej.

Używając w odpowiedni sposób tablicy R oraz własności symetrii palindromu algorytm Manachera wykorzystuje sprytnie informację o wcześniej wyznaczonych promieniach palindromów maksymalnych do wyszukiwania następnych palindromów. Otóż po wyznaczeniu promienia r_P palindromu na pozycji i-tej w łańcuchu s, sprawdzane są promienie palindromów na kolejnych pozycjach poprzedzających pozycję i-tą w obszarze podsłowa w – tutaj algorytm wymaga dwóch wersji – osobnej dla palindromów parzystych i osobnej dla nieparzystych. Zasada jest identyczna dla obu wersji. Rozważmy zatem możliwe przypadki (dla palindromu parzystego):

Na pozycji i-k, k = 1, 2, …, r_P, promień palindromu wynosi 0 – czyli nie istnieje palindrom o środku na pozycji i-k. Skoro tak, to przez symetrię wnioskujemy, iż na pozycji lustrzanej i+k również nie będzie żadnego palindromu. Pozycja i+k możne zostać pominięta przy dalszym wyszukiwania palindromów.

Na pozycji i-k jest palindrom o promieniu r < r_P-k. Taki palindrom w całości zawiera się wewnątrz rozważanego palindromu i co więcej, nie styka się z jego brzegiem. Poprzez symetrię wnioskujemy, iż na pozycji i+k również musi występować taki sam palindrom, którego już dalej nie da się rozszerzyć. Pozycji i+k nie musimy już dalej sprawdzać.

Na pozycji i-k jest palindrom o promieniu r > r_P-k. Taki palindrom wykracza z lewej strony poza obszar rozważanego palindromu. Na pozycji i+k znajduje się palindrom o promieniu r = r_P-k i palindromu tego nie da się już rozszerzyć. Wyjaśnienie tego faktu jest bardzo proste: gdyby palindrom na pozycji i+k posiadał większy promień niż wyliczone r, to również z uwagi na symetrię przeglądany palindrom posiadałby promień większy od r_P, a przecież jest to palindrom maksymalny. Pozycję i+k również możemy pominąć.

Pozostał ostatni przypadek – na pozycji i-k występuje palindrom o promieniu r = r_P-k. Taki sam palindrom musi być na pozycji i+k, jednakże w tym przypadku palindrom ten może być rozszerzalny. Pozycję i+k musimy zatem sprawdzić na obecność palindromu o promieniu większym od r.

Z powyższych rozważań otrzymujemy następujący algorytm działający w czasie liniowym O(n):

Algorytm Manachera wyszukiwania palindromów

Wejście:

s : łańcuch tekstowy.

Wyjście:

Wszystkie palindromy zawarte w łańcuchu s.

Elementy pomocnicze:

i : indeksy środków palindromów; i ∈ N.
j : indeksuje wymiar tablicy R. Wartość 0 dotyczy palindromów parzystych, wartość 1 dotyczy palindromów nieparzystych; j ∈ N.
k : zmienna pomocnicza do indeksowania środków palindromów wewnętrznych; k ∈ N.
r_P : wyznaczany promień palindromu maksymalnego; r_P ∈ N.
n : długość łańcucha s; n ∈ N.
R : tablica dwuwymiarowa, pierwszy wymiar określa rodzaj palindromu, drugi wymiar zawiera indeksy od 0 do n; R ∈ N.
max(x, y) : zwraca większą z wartości x i y.
min(x, y) : zwraca mniejszą z wartości x i y.

Lista kroków:

K01: n ← |s| ; obliczamy długość łańcucha s
K02: s ← w₁+s+w₂ ; na początku i na końcu s dodajemy wartowników, w₁ ≠ w₂
K03: Dla j = 0, 1: ; wyznaczamy promienie palindromów parzystych i nieparzystych
     wykonuj kroki K04…K17
K04:   R[j, 0] ← 0 ; pierwszy promień jest zawsze zerowy
K05:   i ← 1 ; ustawiamy i na pierwszym znaku s za wartownikiem w₁
K06:   r_P ← 0 ; początkowy promień palindromu jest zerowy
K07:   Dopóki i ≤ n: ; przechodzimy przez kolejne środki palindromów
       wykonuj kroki K08…K17
K08:     Dopóki s[i-r_P-1] = s[i+j+r_P]: ; wyznaczamy promień maksymalnego
         wykonuj r_P ← r_P+1 ; palindromu o środku na pozycji i-tej
K09:     R[j, i] ← r_P ; wyliczony promień zapamiętujemy w tablicy R
K10:     k ← 1 ; przeglądamy promienie wcześniejszych palindromów wewnętrznych
K11:     Jeśli R[j, i-k] = r_P-k, ; sprawdzamy ostatni przypadek
         to idź do kroku K16
K12:     Jeśli k ≥ r_P, ; musimy być wewnątrz palindromu
         to idź do kroku K16
K13:     R[j, i+k] ← min(R[j, i-k], r_P-k) ; wyznaczamy promień lustrzanego
         ; palindromu wewnętrznego
K14:     k ← k+1 ; przechodzimy do następnego palindromu wewnętrznego
K15:     Idź do kroku K11
K16:     r_P ← max(r_P-k, 0) ; wyznaczamy promień początkowy palindromu
K17:     i ← i+k ; pomijamy wyliczone palindromy lustrzane
K18:   s ← s[1:n ] ; usuwamy wartowników w₁ i w₂ z łańcucha s
K19:   Dla i = 1, 2, …, n: ; wyprowadzamy kolejne palindromy parzyste i nieparzyste
       wykonuj kroki K20…K21
K20:     Dla j = 0, 1:
         wykonuj krok K21
K21:       Dla r_P = R[j, i], R[j, i]-1, …, 1, 
           wykonuj: pisz s[i-r_P-1:i+2r_P+j]
K22: 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 generuje 40 znakowy łańcuch zbudowany ze znaków {A, B, C, D}, wyszukuje w nim wszystkie palindromy i wypisuje je z odpowiednim przesunięciem.

Pascal

// Wyszukiwanie palindromów
// algorytmem Manachera
// Data: 12.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

uses Math;

const N = 40; // długość łańcucha s

var
  s : ansistring;
  i, j, rp, k : integer;
  R : array [0..1, 1..N+1] of integer;

begin

  // generujemy łańcuch s
  randomize;
  s := '';
  for i := 1 to N do
    s := s+chr(65+random(4));

  // wypisujemy łańcuch s
  writeln(s);

  // szukamy palindromów
  s := '@'+s+'#'; // wstawiamy wartowników
  for j := 0 to 1 do
  begin
    R[j, 1] := 0; i := 2; rp := 0;
    while i <= N+1 do
    begin
      while s[i-rp-1] = s[i+j+rp] do
        inc(rp);
      R[j, i] := rp;
      k := 1;
      while(R[j, i-k] <> rp-k) and (k < rp) do
      begin
        R[j, i+k] := min(R[j, i-k], rp-k);
        inc(k);
      end;
      rp := max(rp-k, 0);
      inc (i, k);
    end;
  end;

  s := copy(s, 2, N); // usuwamy wartowników

  // prezentujemy wyliczone palindromy
  for i := 2 to N+1 do
  begin
    for j := 0 to 1 do
      for rp := R[j, i] downto 1 do
      begin
        for k := 3 to i-rp do write(' ');
        writeln(copy(s, i-rp-1, 2*rp+j));
      end;
  end;
  writeln;
end.

C++

// Wyszukiwanie palindromów
// algorytmem Manachera
// Data: 12.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

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

using namespace std;

const int N = 40; // długość łańcucha s

int main()
{
  string s;
  int i, j, rp, k, R[2][N+1];

  // generujemy łańcuch s
  srand(time(NULL));
  s = "";
  for(i = 0; i < N; i++)
    s += char(65+rand()%4);

  // wypisujemy łańcuch s
  cout << s << endl;
 
  // szukamy palindromów
  s = "@"+s+"#"; // wstawiamy wartowników
  for(j = 0; j <= 1; j++)
  {
    R[j][0] = rp = 0; i = 1;
    while(i <= N)
    {
      while(s[i-rp-1] == s[i+j+rp]) rp++;
      R[j][i] = rp;
      k = 1;
      while((R[j][i-k] != rp-k) && (k < rp))
      {
        R[j][i+k] = min(R[j][i-k], rp-k);
        k++;
      }
      rp = max(rp-k, 0);
      i += k;
    }
  }

  s = s.substr(1, N); // usuwamy wartowników

// prezentujemy wyliczone palindromy

  for(i = 1; i <= N; i++)
  {
    for(j = 0; j <= 1; j++)
      for(rp = R[j][i]; rp > 0; rp--)
      {
        for(k = 1; k < i-rp; k++)
          cout << " ";
        cout << s.substr(i-rp-1, 2*rp+j)
             << endl;
      }
  }
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie palindromów
' algorytmem Manachera
' Data: 12.08.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Function max(Byval a As Integer, _
             Byval b As Integer) _
             As Integer
  If a > b Then
    Return a
  Else
    Return b
  End If
End Function

Function min(Byval a As Integer, _
             Byval b As Integer) _
             As Integer
  If a < b Then
    Return a
  Else
    Return b
  End If
End Function

Const N = 40 ' długość łańcucha s

Dim As String s
Dim As Integer i, j, rp, k, R(1, N+1)

' generujemy łańcuch s
Randomize
s = ""
For i = 1 To N
  s += Chr(65+Cint(Rnd*3))
Next

' wypisujemy łańcuch s
Print s

' szukamy palindromów
s = "@"+s+"#" ' wstawiamy wartowników
For j = 0 To 1
  R(j, 1) = 0: i = 2: rp = 0
  While i <= N+1
    While Mid(s, i-rp-1, 1) = Mid(s, i+j+rp, 1)
      rp += 1
    Wend
    R(j, i) = rp
    k = 1
    while(R(j, i-k) <> rp-k) And (k < rp)
      R(j, i+k) = min(R(j, i-k), rp-k)
      k += 1
    Wend
    rp = max(rp-k, 0)
    i += k
  Wend
Next
s = Mid(s, 2, N) ' usuwamy wartownikw

' prezentujemy wyliczone palindromy
For i = 2 To N+1
  For j = 0 To 1
    For rp = R(j, i) To 1 Step -1
      For k = 3 To i-rp
        Print " ";
      Next
      Print Mid(s, i-rp-1, 2*rp+j)
    Next
  Next
Next
Print
End

Python (dodatek)

# Wyszukiwanie palindromów
# algorytmem Manachera
# Data: 23.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 40 # długość łańcucha s

# tworzymy tablicę R
r = [[0 for j in range(N+1)] for i in range(2)]
# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(65, 69))
# wypisujemy łańcuch s
print(s)
# szukamy palindromów
s = "@"+s+"#" # wstawiamy wartowników
for j in range(2):
    r[j][0], rp, i = 0, 0, 1
    while i <= N:
        while s[i-rp-1] == s[i+j+rp]:
            rp += 1
        r[j][i], k = rp, 1
        while (r[j][i-k] != rp-k) and (k < rp):
            r[j][i+k] = min(r[j][i-k], rp-k)
            k += 1
        rp = max(rp-k, 0)
        i += k
s = s[1:-1] # usuwamy wartowników

# prezentujemy wyliczone palindromy
for i in range(1, N+1):
    for j in range(2):
        for rp in range(r[j][i], 0, -1):
            for k in range(1, i-rp):
                print(" ", end="")
            print(s[i-rp-1:i-1+rp+j])
print()

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 palindromów

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania palindromów

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm Manachera wyszukiwania palindromów

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy