algorytm.org

Wyszukiwanie liczby palindromów w tekście.

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Wyszukiwanie liczby palindromów w tekście.
Ocena użytkowników:***** / 6
SłabyŚwietny 
Wpisany przez Rafał Świetlicki, 09 maja 2007 19:32

Palindrom jest to wyraz, który jest taki sam niezależnie od której strony go czytamy, np.: kajak.
Niech s = s1s2... sn będzie słowem długości n, (n ≥ 1) nad dowolnym alfabetem. Zadaniem jest obliczyć, dla ilu par liczb całkowitych (i, j), (1 ≤ i ≤ j ≤ n) słowo sisi+1... sj jest palindromem.
Przykład: dla słowa "mama" wynik będzie równy 6 i składać się będą na niego następujące słowa: "m", "a", "m", "a", "mam", "ama". Rozwiązanie tego problemu będzie oparte na ideach programowania dynamicznego.
Niech M będzie dwuwymiarową tablicą logiczną taką, że Mi, j = true (1 ≤ i ≤ j ≤ n) jeżeli słowo sisi+1... sj jest palindromem zaś w przeciwnym razie Mi, j = false. Jak łatwo zauważyć, jeśli dla pewnych indeksów i, j (1 ≤ i < j ≤ n) słowo si+1si+2... sj-1 jest palindromem, to słowo sisi+1... sj jest palindromem wtedy i tylko wtedy, gdy si = sj (domyślnie przyjmujemy, że słowo puste oraz słowo złożone z jednego znaku jest palindromem). Stąd dostajemy:
  • Mi, i = true, 1 ≤ i ≤ n
  • Mi, j = (Mi+1, j–1 AND (si = sj)), 1 ≤ i < j ≤ n

Maksymalna liczbę palindromów, jaką można otrzymać ze słowa długości n wynosi n(n+1)/2 i jest osiągnięta, gdy słowo s składa się z n jednakowych znaków.

Postawmy teraz problem nieco bardziej złożony. Dla danego słowa s = s1s2... sn długości n, (n ≥ 1) nad dowolnym alfabetem zadaniem jest obliczyć, na ile sposobów można wybrać liczby całkowite, k, i1, i2, ..., ik (1 ≤ k ≤ n, 1 ≤ i1 < i2 < ... < ik ≤ n) takie, że słowo si1si2... sik jest palindromem.
Przykład: dla słowa "mama" wynik będzie równy 8 i składać się będą na niego następujące słowa: "m", "a", "m", "a", "mm", "aa", "mam", "ama".
Rozwiązanie tego problemu będzie również oparte na ideach programowania dynamicznego. Niech M będzie dwuwymiarową tablicą taką, że element Mi, j (1 ≤ i ≤ j ≤ n) będzie równy ilości sposobów wyboru liczb całkowitych k, i1, i2, ..., ik (1 ≤ k ≤ n, i ≤ i1 < i2 < ... < ik ≤ j ) takich, że słowo si1si2... ik jest palindromem. Wówczas rozwiązaniem postawionego problemu będzie wartość M1, n. Oczywiście Mi, i = 1, 1 ≤ i ≤ n.
Zastanówmy się teraz, o ile liczba Mi, j będzie większa od liczby Mi+1, j (1 ≤ i < j ≤ n). Na pewno o przynajmniej 1 gdyż element si sam będzie stanowić nowy palindrom. Poza tym, jeżeli dla pewnego k, (i+1 ≤ k ≤ j) zachodzi równość si = sk to różnica Mi, j – Mi+1, j zwiększy się także o ilość palindromów zawartych w słowie si+1si+2...sk-1 powiększoną o jeden. Wprowadzimy funkcję f(i, j), której wartość będzie zdefiniowana następująco:
  • 1, jeżeli si = sj
  • 0, w przeciwnym razie

Reasumując:
  • Mi, i = 1, 1 ≤ i ≤ n
  • Mi, j = Mi+1, j + 1 + f(i, i+1)(Mi+1, i + 1) + f(i, i+2)(Mi+1, i+1 + 1)... + f(i, j)(Mi+1, j-1 + 1), 1 ≤ i < j ≤ n
Maksymalna ilość palindromów, jaką można otrzymać ze słowa długości n wynosi 2n - 1 i jest osiągnięta, gdy słowo s składa się z n jednakowych znaków.



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 0
Rafał ŚwietlickiC/C++
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 19 lipca 2011 12:05
Komentarze
photo
+1 # marseel 2010-07-02 20:22
Chciałbym tylko dodać, że liczenie wszystkich spójnych palindromów można wykonać w czasie liniowym ze względu na długość słowa stosując algorytm Manachera
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz