[Algorytmy] Najkrótszy okres słowa

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: matinf »

Witam,
Czy istnieje jakaś pomocna struktura danych która pomoże mi szukać najkrótszego okresu słowa.
Z tym że tych słów będzie dużo więć \(\displaystyle{ O(n^2)}\) odpada ;(.
Czekam na propozycje
Ostatnio zmieniony 1 lip 2012, o 12:38 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: paladin »

Wystarczy policzyć tablicę prefiksowo-sufiksową (znaną też jako "tablica \(\displaystyle{ \pi}\)", "tablica KMP" albo "partial match", nie mylić z tablicą sufiksową!). Ona przy okazji wyznacza najkrótszy okres słowa.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: matinf »

Tak, myślałem o tym, jednak jedno mi nie pasuje w tym. Funkcja P znajdzie nam najdłuższe właściwe prefixo-sufixy dla słów: s[1...n], s[1..n-1], s[1...n-2]......... itd
ale jeśli ja dostanę pytanie o słowo s[5...9] ?
Ostatnio zmieniony 1 lip 2012, o 12:39 przez Afish, łącznie zmieniany 1 raz.
Powód: Stosuj tagi.
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: paladin »

Ach, chodzi o okresy podsłów danego słowa. Czyżby to zadanie?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: matinf »

zadanie analogia
ale nie to miałem na myśli
JumpSmerf
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 2 lip 2011, o 15:32
Płeć: Mężczyzna
Lokalizacja: Hrubieszów/Kraków
Podziękował: 2 razy
Pomógł: 9 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: JumpSmerf »

Na OI-u napisałem tylko rozwiązanie za 30 pkt., ale wydaje mi się, że w tym zadaniu przydatne będzie haszowanie lub algorytm KMR. W każdym razie na pewno odpowiedź znajdziesz tutaj:
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: paladin »

Hm, to co miałeś na myśli?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Najkrótszy okres słowa

Post autor: matinf »

źle się wyraziłem, w moim zadaniu chodzi o to samo
tyle, ze nie rozwiazuję tego pod to
ODPOWIEDZ