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

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

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 Rpalindrom parzysty ( ang. even palindrome ), lub
s  = wXw Rpalindrom 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.

Rozwiązanie nr 1

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 3 ), 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.

Zmienne 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:
wykonuj kroki K03...K10
przeglądamy łańcuch s
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,
        wykonuj kroki K07...K09
sprawdzamy, czy podsłowo jest palindromem
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 <time.h>

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 ( ( unsigned )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
Wynik:
BCACCAABCBBDCCCCDBBBDBDDBDCDBBCBADBBBABB
 CAC
  ACCA
   CC
     AA
       BCB
         BB
         BBDCCCCDBB
          BDCCCCDB
           DCCCCD
            CC
            CCC
            CCCC
             CC
             CCC
              CC
                DBBBD
                 BB
                 BBB
                  BB
                   BDB
                    DBD
                    DBDDBD
                     BDDB
                      DD
                       DBD
                        BDCDB
                         DCD
                            BB
                             BCB
                                  BB
                                  BBB
                                   BB
                                   BBABB
                                    BAB
                                      BB
Wyszukiwanie palindromów
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

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 ):

obrazek

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.

obrazek

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ć.

obrazek

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ąć.

obrazek

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.

Zmienne 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

Lista kroków:

K01: n  ← | s | obliczamy długość łańcucha s
K02: s  ← w 1 + s  + w 2 na początku i na końcu s dodajemy wartowników, w 1 ≠ w 2
K03: Dla j  = 0, 1:
wykonuj kroki K04...K17
wyznaczamy promienie palindromów parzystych i nieparzystych
K04:     R [ j, 0 ] ← 0 pierwszy promień jest zawsze zerowy
K05:     i  ← 1 ustawiamy i na pierwszym znaku s za wartownikiem w 1
K06:     r p  ← 0 początkowy promień palindromu jest zerowy
K07:     Dopóki i  ≤ n,
    wykonuj kroki K08...K17
przechodzimy przez kolejne środki palindromów
K08:         Dopóki s [ i - r p - 1 ] = s [ i  + j  + r p  ],
        wykonuj r p  ← r p  + 1
wyznaczamy promień maksymalnego 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,
        to idź do kroku K16
sprawdzamy ostatni przypadek
K12:         Jeśli k  ≥ r p,
        to idź do kroku K16
musimy być wewnątrz palindromu
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 1 i w 2 z łańcucha s
K19: Dla i  = 1, 2, ..., n :
wykonuj kroki K20...K21
wyprowadzamy kolejne palindromy parzyste i nieparzyste
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 <time.h>

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 ( ( unsigned )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 wartowników

' 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
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.