Algorytmy wyszukiwania ciągów

Question

Dla algorytmów wyszukiwania dwóch ciągów znaków: KMP i drzewo przyrostków, które jest preferowane w jakich przypadkach? Podaj kilka praktycznych przykładów.

Answer 1

Drzewo przyrostków jest lepsze, jeśli będziesz musiał odpowiedzieć na wiele pytań, takich jak "czy igła jest obecna w stogu siana?". KMP jest lepszy, jeśli szukasz tylko jednego ciągu w innym pojedynczym łańcuchu i nie musisz tego robić wiele razy.

Drzewo sufiksów jest o wiele bardziej ogólną strukturą danych, dzięki czemu można z nim znacznie więcej. Zobacz, co możesz z nim zrobić: here. KMP jest użyteczny do wyszukiwania, czy łańcuch jest podłańcuchem w innym ciągu.

Możesz także chcieć sprawdzić inne algorytmy, takie jak Boyer-Moore, Rabin-Karp, a nawet algorytm naiwny, ponieważ istnieją sytuacje (wejścia), w których jedna jest lepsza od innych.

Konkluzja brzmi:

1. Jeśli masz dużo zapytań jak ten, o którym wspomniałem powyżej, warto zbudować drzewo przyrostek, a następnie odpowiedzieć na każde zapytanie szybciej.
2. Jeśli potrzebujesz więcej niż tego typu zapytań, warto zbudować drzewo sufiksów.
3. Jeśli zależy Ci jedynie na okazyjnym poszukiwaniu, czy łańcuch jest podciągiem innego łańcucha, użyj KMP.