Algoritmi za podudaranje znakovnih nizova : završni rad - Maršić, Marin (M. Maršić, 2016)
Sažetak na hrvatskom: U ovom radu obradili smo najosnovnije metode za podudaranje znakovnih nizova i kompresiju teksta. Za svaki od ovih tipova analizirali smo nekoliko najbitnijih algoritama. Algoritme za podudaranje znakovnih nizova podijelili smo na one za egzaktno i aproksimativno podudaranje. Algoritmi egzaktnog podudaranja tražili su dani znakovni uzorak u tekstu, dok su algoritmi aproksimativnog podudaranja tražili riječi slične našem uzorku. Osim naivnog algoritma za egzaktno podudaranje znakovnih nizova, obradili smo i Rabin-Karpov, Knuth-Morris-Prattov, Boyer-Mooreov algoritam te strukturu podataka sufiksnog stabla koja ima veliku primjenu na ovom problemu. Za rješavanje problema aproksimativnog podudaranja koristili smo algoritam računanja edit udaljenosti. Na kraju smo obradili tri algoritma za kompresiju teksta: Shannon-Fanoov, Huffmanovi i Lempel–Ziv–Welshev.