[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 » 30 cze 2012, o 23:06

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 » 1 lip 2012, o 03:09

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 » 1 lip 2012, o 09:35

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 » 1 lip 2012, o 09:50

Ach, chodzi o okresy podsłów danego słowa. Czyżby to zadanie?
http://main.edu.pl/pl/archive/oi/19/okr

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 » 1 lip 2012, o 11:12

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 » 1 lip 2012, o 16:45

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: http://was.zaa.mimuw.edu.pl/?q=node/40

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 » 1 lip 2012, o 17:03

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 » 1 lip 2012, o 17:35

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

ODPOWIEDZ