Wyszukiwanie palindromów


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
  Rozwiązanie 1
Rozwiązanie 2

 

Problem

W łańcuchu s 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 opracowaniu.

 

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

 

Przykład:

s   = ABCD
sR = DCBA

 

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

 

s = wwRpalindrom parzysty (ang. even palindrome), lub
s = wXwRpalindrom 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 wwR lub wXwR. 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 = wwR, lub p = wXwR

 

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(n3), 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
iP  – prawy indeks, iP N
iL  – lewy indeks, iL N
Lista kroków:
K01: n ← |s|  
K02: Dla i = 0,1,...,n - 2, wykonuj K03...K10 ; przeglądamy łańcuch s
K03:     Dla j = i+2, i+3,...,n-1: wykonuj K04...K10  
K04:         iLi ; lewy indeks na pierwszym znaku podsłowa
K05:         iPj - 1 ; prawy indeks na ostatnim znaku podsłowa
K06:         Dopóki iL < iP wykonuj K07...K09 ; sprawdzamy, czy podsłowo jest palindromem
K07:             Jeśli s[iL] ≠ s[iP], to następny obieg pętli K03  
K08:             iLiL + 1 ; lewy indeks przesuwamy w prawo
K09:             iPiP - 1 ; a prawy w lewo
K10:         Pisz s[i,j] ; wyprowadzamy znaleziony palindrom
K11: Zakończ  

 

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 40 znakowy łańcuch zbudowany ze znaków {A,B,C,D}, wyszukuje w nim wszystkie palindromy i wypisuje je z odpowiednim przesunięciem.

 

Lazarus
// Wyszukiwanie palindromów
// Data: 9.08.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie palindromów
// Data: 9.08.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie palindromów
' Data: 9.08.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 

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 pP będzie palindromem parzystym o postaci pP = wwR, gdzie w jest niepustym podłańcuchem.
Niech pN będzie palindromem nieparzystym o postaci pN = wXwR.

 

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

Palindrom parzysty pP posiada zawsze długość |pP| = 2rp. Palindrom nieparzysty pN posiada zawsze długość |pN| = 2rp + 1.

Środkiem palindromu p jest pozycja is = rp – 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 wR, natomiast dla palindromu nieparzystego środek wypadnie na znaku X:

 

pP[rp] = wR[0]
pN[rp] = 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:

rp 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 rp 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,...,rp, 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 < rp - 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 > rp - k. Taki palindrom wykracza z lewej strony poza obszar rozważanego palindromu. Na pozycji i + k znajduje się palindrom o promieniu r = rp - 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 rp, 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 = rp - 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
rp  – wyznaczany promień palindromu maksymalnego, rp 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 ← w1 + s + w2 ; na początku i na końcu s dodajemy wartowników, w1 ≠ w2
K03: Dla j = 0,1 wykonuj 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 w1
K06:     rp ← 0 ; początkowy promień palindromu jest zerowy
K07:     Dopóki i ≤ n, wykonuj K08...K17 ; przechodzimy przez kolejne środki palindromów
K08:         Dopóki s[i - rp - 1] = s[i + j + rp],
        wykonuj rprp + 1
; wyznaczamy promień maksymalnego palindromu o środku
; na pozycji i-tej
K09:         R[j,i] ← rp ; 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] = rp - k, to idź do K16 ; sprawdzamy ostatni przypadek
K12:         Jeśli krp, to idź do K16 ; musimy być wewnątrz palindromu
K13:         R[j,i + k] ← min(R[j,i - k],rp - k) ; wyznaczamy promień lustrzanego palindromu wewnętrznego
K14:         kk + 1 ; przechodzimy do następnego palindromu wewnętrznego
K15:         Idź do K11  
K16:         rp ← max(rp - k,0) ; wyznaczamy promień początkowy palindromu
K17:         ii + k ; pomijamy wyliczone palindromy lustrzane
K18: ss[1:n] ; usuwamy wartowników w1 i w2 z łańcucha s
K19: Dla i = 1,2,...,n wykonuj K20...K21 ; wyprowadzamy kolejne palindromy parzyste i nieparzyste
K20:     Dla j = 0,1 wykonuj K21  
K21:         Dla rp = R[j,i], R[j,i ]- 1,...,1 pisz s[i - rp - 1:i + 2rp + j]  
K22: Zakończ  

 

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 40 znakowy łańcuch zbudowany ze znaków {A,B,C,D}, wyszukuje w nim wszystkie palindromy i wypisuje je z odpowiednim przesunięciem.

 

Lazarus
// Wyszukiwanie palindromów algorytmem Manachera
// Data: 12.08.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie palindromów algorytmem Manachera
// Data: 12.08.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie palindromów algorytmem Manachera
' Data: 12.08.2008
' (C)2012 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

 



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.