Zaawansowane algorytmy i struktury danych/Ćwiczenia 1

From Studia Informatyczne

Spis treści

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\ =\  (ba^kba^k)^k, gdzie usuwamy ostatni symbol oraz x\ =\ ba^{k-1}ba^{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.