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): 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 |
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 = [[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() |
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.