Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemW łańcuchu s należy znaleźć wszystkie palindromy o długości większej Przez palindrom (ang. palindrome)
rozumiemy łańcuch Przykład: ABBCBBA – 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
Wprowadźmy symbol sR, który oznacza łańcuch znakowy o odwróconej kolejności znaków w stosunku
Przykład: s = ABCD Łańcuch s jest palindromem, jeśli da się rozłożyć na dwa
podłańcuchy s = wwR
–
palindrom parzysty (ang. even palindrome), lub Przykład: ABCDDCBA – palindrom parzysty →
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ę |
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
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
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: iL ← i ; lewy indeks na pierwszym znaku podsłowa K05: iP ← j-1 ; prawy indeks na ostatnim znaku podsłowa K06: Dopóki iL < iP, ; sprawdzamy, czy podsłowo jest palindromem wykonuj kroki K07…K09 K07: Jeśli s[iL] ≠ s[iP], to następny obieg pętli K03 K08: iL ← iL + 1 ; lewy indeks przesuwamy w prawo K09: iP ← iP - 1 ; a prawy w lewo K10: Pisz s[i,j] ; wyprowadzamy znaleziony palindrom K11: Zakończ
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
|
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. |
// 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): iL,iP,t = i,j-1,True while iL < iP: if s[iL] != s[iP]: t = False break iL += 1 iP -= 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 |
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
Niech pN będzie palindromem nieparzystym o postaci
Promieniem rP
Palindrom
Środkiem
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
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ę
R[0, …] – promienie palindromów parzystych R[1, …] – promienie palindromów nieparzystych
Indeksy tych tablic określają kolejne pozycje znakowe
Używając w odpowiedni sposób
Na pozycji i -
k,
Na pozycji i -
k jest palindrom o promieniu
Na pozycji i -
k jest palindrom o promieniu
Pozostał ostatni przypadek – na pozycji
Z powyższych rozważań otrzymujemy następujący algorytm działający w czasie liniowym
Wszystkie palindromy zawarte
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: ; 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 w1 K06: rP ← 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-rP-1] = s[i+j+rP]: ; wyznaczamy promień maksymalnego wykonuj rP ← rP+1 ; 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, ; sprawdzamy ostatni przypadek to idź do kroku K16 K12: Jeśli k ≥ rP, ; musimy być wewnątrz palindromu to idź do kroku K16 K13: R[j,i+k] ← min(R[j,i-k],rP-k) ; wyznaczamy promień lustrzanego ; palindromu wewnętrznego K14: k ← k+1 ; przechodzimy do następnego palindromu wewnętrznego K15: Idź do kroku K11 K16: rP ← max(rP-k,0) ; wyznaczamy promień początkowy palindromu K17: i ← i+k ; pomijamy wyliczone palindromy lustrzane K18: s ← s[1:n ] ; usuwamy wartowników w1 i w2 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 rP = R[j, i],R[j,i]-1,…,1: wykonuj pisz s[i-rP-1:i+2rP+j] K22: Zakończ
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 |
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. |
// 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 = [] for i in range(2): a = [] for j in range(N+1): a.append(0) R.append(a) # 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() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.