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 czasie 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 zaś 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 czasie 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 jest to bardzo duże przesunięcie, jeśli tak, to jest 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

.

Weźmy $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 w przybliżeniu $3n$, gdzie $n=(2k+2)*k-1$ jest długością $y$.