KMP – wyszukiwanie wzorca w tekście


Gdy chcemy wyszukać w tekście jakiś wzorzec, możemy użyć najprostszego rozwiązania brutalnego: iteruję się po wszystkich literach tekstu, jeśli dana litera pokrywa się ze wzorcem, to sprawdzam czy reszta również się pokrywa. Jeżeli tak, oznacza to, że znalazłem wystąpienie wzorca, w przeciwnym wypadku: nie. Niestety takie rozwiązanie jest nieoptymalne i przy danych wejściowych o dużym rozmiarze, np. tekst o długości 10^6 + wzorzec o długości 10^4 , możemy nie doczekać się naszego wyniku. Na szczęście istnieje algorytm działający w złożoności liniowej, jednak zanim do niego przejdziemy musimy nauczyć się tworzenia tablicy prefikso-sufiksów.

Czym są prefikso-sufiksy?

Aby wytłumaczyć czym są prefikso-sufiksy, posłużę się przykładem tekstu:
S = „ababxabab”
Prefikso-sufiksem nazywamy prefiks tekstu, który jest jednocześnie jego sufiksem. W przykładzie prefikso-sufiksami są: „ab”, „abab” oraz „ababxabab”.
Właściwym prefikso-sufiksem jest prefikso-sufiks, który nie jest całym tekstem. W przykładzie: „ab” oraz „abab”.
Maksymalny prefikso-sufiks to najdłuższy prefikso-sufiks. W przykładzie: „ababxabab”.
Maksymalnym właściwym prefikso-sufiksem nazywamy najdłuższy prefikso-sufiks właściwy. W przykładzie: „abab”.

Uwaga!
W dalszej części artykułu, gdy będę posługiwał się pojęciem prefikso-sufiksu, to będę mieć na myśli prefikso-sufiks właściwy.

Tablica prefikso-sufiksów

Jak już wspomniałem, do algorytmu KMP potrzebujemy tablicy prefikso-sufiksów – dla każdego indeksu i od 0 do S.size() – 1 będziemy przechowywać następującą informację: jaka jest długość maksymalnego prefikso-sufiksu, gdzie tekstem jest fragment od 0 do i. Aby utworzyć taką tablicę w liniowej złożoności, musimy poznać dwa lematy.

Lemat 1.

Prefikso-sufiks mojego prefikso-sufiksu jest moim prefikso-sufiksem.

Innymi słowy: mam tekst, znajduję w nim prefikso-sufiks, to jego prefikso-sufiks będzie prefikso-sufiksem dla całego tekstu. Poza tym, zauważmy że jeżeli mamy wyliczoną tablicę prefikso-sufiksów ps, to zbiorem wszystkich prefisko-sufiksów tekstu S jest zbiór: {ps [S.size()-1], ps [ ps [S.size()-1 ] ], …}, gdzie każdy element zbioru jest >= 1.

Żółty i niebieski prefikso-sufiks są prefisko-sufiksami dla całego tekstu.

Lemat 2.

Niech t będzie długością najdłuższego prefikso-sufiksu słowa S[0…i-1], takiego że S[i]==S[t]. Wtedy maksymalny prefikso-sufiks słowa S[0…i] będzie mieć długość t + 1.

Skoro poznaliśmy już dwa lematy, to możemy przejść do naszego algorytmu na znalezienie tablicy prefikso-sufiksów:

KMP

Aby wyszukać wzorzec w tekście wystarczy wykonać powyższy algorytm dla następującego tekstu: wzorzec + znak, który nie występuje ani we wzorcu ani w tekście, np. „#” + tekst do przeszukania. Tam, gdzie ps [ i ] jest równe długości wzorca, oznacza to, że w miejscu i kończy się wzorzec wyszukany w tekście. Dzięki temu jesteśmy w stanie stwierdzić, w których miejscach i ile razy wystąpił wzorzec.

Karen and Coffee – omówienie

Treść zadania

https://codeforces.com/problemset/problem/816/B

O co chodzi w zadaniu?

Dostajemy liczbę n, k i q oznaczające liczbę recept, minimalną liczbę recept żeby temperatura była zarekomendowana, oraz liczbę zapytań. Po wczytaniu tych trzech liczb otrzymujemy n recept i q par przedziałów temperatur. Naszym zadaniem jest wypisanie dla każdego przedziału liczby temperatur których ilość w receptach jest >= k.

Jak się za to zabrać?

Załóżmy, że mamy dostęp w czasie stałym do liczby poprawnych recept w danym przedziale, wtedy nasz problem problem stałby się prosty, gdyż wczytując przedziały wystarczyłoby wypisać naszą liczbę w czasie stałym.

Jednak jak stworzyć taką strukturę danych z wcześniej podanych liczb?

Otóż mamy dwa potężne narzędzia, które pomogą nam w rozwiązaniu tego problemu, są to sumy prefiksowe i zliczanie elementów.

Tak więc najpierw analizujemy wszystkie recepty, na przykład dla recepty o sugerującej temperatury na przedziale:  [2, 5] musimy zwiększyć tab[2] o jeden i zmniejszyć tab[6] o jeden, gdyż dzięki tak zainicjowanej tablicy możemy uzupełnić ją liniowo dodając do każdej komórki poprzednią wartość. Dla wartości:

1 3

4 5

5 6

3 9

Otrzymamy:

0 1 0  0 1 1 -1 -1 0 0  -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

A po policzeniu sum prefiksowych:

0 1 1 1 2 3 2 1 1 1   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Gdy już to zrobimy nasze rozwiązanie jest prawie gotowe, gdyż w czasie liniowym potrafimy znaleźć odpowiedź dla dowolnego przedziału.

Jednak nie jest to czas stały więc dla wielu przedziałów wciąż będziemy mieli złożoność kwadratową. Dlatego też musimy stworzyć tablice sum prefiksowych, dzięki której wyznaczenie wartości w dowolnym przedziale będzie się odbywało w czasie stałym, a całe rozwiązanie w liniowym.

Tak więc mając powyższą tablicę tworzymy nową tablicę (bądź zapełniamy tą) zerami i jedynkami, w następujący sposób:

Jeśli wartość w tablicy o indeksie i jest >= k to zapisujemy w nowej tablicy jeden, w przeciwnym wypadku zero.

Dla takiego przykładu:

4 2 2

1 3

4 5

5 6

3 9

4 6

8 10

Nasza tablica będzie zmieniać się następująco:

0 0 0 0 0 0 0 0 0 0   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Uzupełnianie tablicy jedynkami i minus jedynkami:

0 1 0  0 1 1 -1 -1  0 0 -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 1 1 1 2 3 2 1 1 1  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

k = 2, więc dla każdej liczby >= 2  zapisujemy 1, a dla niższych 0

0 0 0 0 1 1 1 0 0 0  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 0 0 0 1 2 3 3 3 3  3 3 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Więc naszym wynikiem będzie:

3

0

Gdyż dla przedziału 4 6 tab[6] – tab[4-1] = tab[6] – tab[3] = 3 – 0 = 3,

oraz dla przedziału 8 10 tab[10] – tab[8-1] = tab[10] – tab[7] = 3 – 3 = 0

Link do kodu

https://ideone.com/jT7Oku

Autor: Michał Woźniak

„Bilet” – omówienie (spójny podciąg o maksymalnej sumie)

O co chodzi w zadaniu?

Jest n miast. Przez wszystkie miasta prowadzi piaszczysta droga jednokierunkowa; na odcinkach tej drogi pomiędzy miastami, Bajtazar sprzedaje swoje towary, na których zyskuje bądź traci. Bajtazar chce się dostać z pierwszego do ostatniego miasta. Ma on również możliwość wsiąść raz w pociąg, który zabierze go do dowolnego innego miasta (również do poprzedniego). Chcemy obliczyć maksymalny zysk Bajtazara.

Jak się do tego zabrać?

Gdyby Bajtazar nie miał możliwości jednokrotnego użycia pociągu, to musiałby przejść przez wszystkie miasta piaszczystą drogą. Co z kolei oznacza, że wynikiem byłaby suma wszystkich zysków i strat. Oznaczmy zbiór odcinków piaszczystej drogi, jako zbiór liter:

a  b  c  d  e  f  g

Do czego sprowadza się użycie pociągu? Do wzięcia jakiegoś podciągu piaszczystej drogi, np. [a  b],    [d  e  f],    [b  c  d  e] i wykonania jednej z dwóch operacji:

  1. Przedłużenia piaszczystej drogi o ten odcinek (cofnięcie się).
  2. Skrócenia piaszczystej drogi o ten odcinek (pojechanie dalej).

Naszym zadaniem jest znalezienie dwóch podciągów: jednego o maksymalnej sumie, drugiego o minimalnej sumie. Ten o maksymalnej sumie będzie oznaczać dodatkową drogę, którą chcemy jeszcze pokonać. Ten o minimalnej, będzie oznaczać drogę, którą chcemy pominąć. Wynikiem końcowym będzie większa wartość z dwóch wariantów:

  1. Suma całej piaszczystej drogi pomniejszona o minimalny podciąg.
  2. Suma całej piaszczystej drogi powiększona o maksymalny maksymalny podciąg.