Algorytmy i struktury danych · Senior · Pytanie 22 z 75
Jak KMP osiąga wyszukiwanie wzorca w O(n + m)?
- 1Z góry haszuje każdy możliwy podnapis tekstu
- ✓Poprawna odpowiedź: Funkcja prefiksowa mówi, o ile przeskoczyć
- 3Sortuje znaki tekstu i szuka wzorca binarnie
Wyjaśnienie
Dla każdej pozycji wzorca funkcja prefiksowa przechowuje długość najdłuższego właściwego prefiksu, który jest też sufiksem. Przy niezgodności wzorzec przeskakuje o tę wartość, więc wskaźnik w tekście nigdy się nie cofa.