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
[Algorytmy] Najkrótszy okres słowa
-
- 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
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] .
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
- paladin
- 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
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.
-
- 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
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:
ale jeśli ja dostanę pytanie o słowo
s[1...n], s[1..n-1], s[1...n-2].........
itdale 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.
Powód: Stosuj tagi.
-
- 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
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: