Zaawansowane algorytmy i struktury danych/Ćwiczenia 1

Zadanie 1

Sprawdz w czasie liniowym czy słowo x jest pierwotne.

Rozwiązanie

.

Za pomocą tablicy prefikso-sufiksów liczymy najkrótszy okres słowa x, następnie sprawdzamy czy jest on dzielnikiem długości x. Można to nawet zrobic bez tablicy prefikso-sufiksów w czasei liniowym i pamięci stałej.

Zadanie 2

Pokaż redukcję w czasie liniowym problemu liczenia tablicy PREF do liczenia tablicy P

Rozwiązanie

.

Zauważmy, że w sytuacji gdy P[i]=k mamy, że $PREF[i-k]\ge k$ Poza bardzo specjalnymi sytuacjami dla pewnego i, k zajdzie tutaj równość dla PREF[i-k].

Zadanie 3

Załóżmy, że wzorzec x jest ustalony, ma długość m, a tekst y w którym szukamy x jest losowym tekstem długości n, alfabet jest binarny. Każdy symbol jest zerem lub jedynką niezależnie z takim samym prawdopodobieństwem 1/2.

Skonstruuj algorytm, który będzie szukał wzorca x w czasei oczekiwanym (średnim) $O(\frac{n\cdot m}{\log m})$

Rozwiązanie

.

Skorzystaj z drzewa sufiksowego i sprawdzaj czy końcowy fragment długości $c\cdot \log m$ kolejnego przyłozenia wzorca jest podsłowem x. Jeśli nie to bardzo duże przesunięcie, jeśli tak to algorytm naiwny. Dobierz odpowiednie c.

Zadanie 4

Udowdnij, że w modelu takim jak w poprzednim zadaniu algorytm BM nie ma złożoności oczekiwanej rzędu mniejszego niż liniowy.

Rozwiązanie

.

Wezmy x składający się z samych liter a, poza kilkom symbolami b na końcu.

Zadanie 5

Pokaż, że jeśli cn jest górnym oszacowaniem liczby porównań w algorytmie BM (dla dostatecznie dużych n) to $c\ge 3$

Rozwiązanie

.

Zastosuj algorytm BM do tekstów: $y=(b{a}^{k}b{a}^k{)}^k$, gdzie usuwamy ostatni symbol,oraz $x=b{a}^{k-1}b{a}^{k-1}$.

Dla tych danych liczba porównań symboli wynosi wprzybliżeniu $3n$, gdzie $n=(2k+2)*k-1$ jest długością $y$.