Топ-100
Back

ⓘ Apostoliko–Đankarlov algoritam



                                     

ⓘ Apostoliko–Dankarlov algoritam

U računarstvu, Apostoliko–Dankarlov algoritam je varijanta Bojer-Murovog algoritma za traženje stringa, čija osnovna primena je traženje pojavljivanja šablona P {\displaystyle P} u tekstu T {\displaystyle T}. Kao i kod drugih poredenja na bazi string pretrage, ovo se izvršava tako što se T {\displaystyle T} namesti na odredeni indeks T {\displaystyle T} i proverava da li postoji poklapanje na tom indeksu. P {\displaystyle P} se onda pomera do T {\displaystyle T} u skladu sa pravilima Bojer-Murvog algoritma, i proces se ponavlja dok se ne dode do kraja T {\displaystyle T}. Primenom Bojer-Murovog pomeranja obično dovodi do toga da se veliki delovi teksta preskaču.

Što se tiče operacija pomeranja, Apostoliko–Dankarlov algoritam je potpuno jednak po funcionalnosti sa Bojer-Murovim algoritmom. Korisnost Apostoliko–Dankarlovog algoritma je da se ubrza operacija proveravanja poklapanja indeksa na bilo kom indeksu. Sa Bojer-Murom, traženje pojavljivanja P {\displaystyle P} u T {\displaystyle T} zahteva da se svih n {\displaystyle n} karaktera iz P {\displaystyle P} eksplicitno poklapa. Za odredene šablone i teksove, ovo je vrlo neefikasno - prost primer je kada se i šablon i tekst sastoje iz istog ponavljanja karaktera, u ovom slučaju Bojer-Murov algoritam ima složenost O n m {\displaystyle Onm} gde je mathm/math dužina karaktera iz T {\displaystyle T}. Apostoliko–Dankarlov algoritam ubrzava ovo tako sto čuva broj karaktera koji se poklapaju na poravnatim mestima iz T {\displaystyle T} u tabelu, i to se spaja sa podacima skupljenih tokom predprocesiranja P {\displaystyle P} da bi se izbegla suvišna poredjenja sekvenci karaktera za koje se zna da se poklapaju.

Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →