Апостолико–Ђанкарлов алгоритам

У рачунарству, Апостолико–Ђанкарлов алгоритам је варијанта Бојер-Муровог алгоритма за тражење стринга, чија основна примена је тражење појављивања шаблона $P$ у тексту $T$. Као и код других поређења на бази стринг претраге, ово се извршава тако што се $T$ намести на одређени индекс $T$ и проверава да ли постоји поклапање на том индексу. $P$ се онда помера до $T$ у складу са правилима Бојер-Мурвог алгоритма, и процес се понавља док се не дође до краја $T$. Применом Бојер-Муровог померања обично доводи до тога да се велики делови текста прескачу.

Што се тиче операција померања, Апостолико–Ђанкарлов алгоритам је потпуно једнак по фунционалности са Бојер-Муровим алгоритмом. Корисност Апостолико–Ђанкарловог алгоритма је да се убрза операција проверавања поклапања индекса на било ком индексу. Са Бојер-Муром, тражење појављивања $P$ у $T$ захтева да се свих $n$ карактера из $P$ експлицитно поклапа. За одређене шаблоне и тексове, ово је врло неефикасно - прост пример је када се и шаблон и текст састоје из истог понављања карактера, у овом случају Бојер-Муров алгоритам има сложеност $O(nm)$ где је (матх)м(/матх) дужина карактера из $T$. Апостолико–Ђанкарлов алгоритам убрзава ово тако сто чува број карактера који се поклапају на поравнатим местима из $T$ у табелу, и то се спаја са подацима скупљених током предпроцесирања $P$ да би се избегла сувишна поредјења секвенци карактера за које се зна да се поклапају.

Литература

• Apostolico A., Giancarlo R., 1986, The Boyer-Moore-Galil string searching strategies revisited, SIAM Journal on Computing. . 15 (1): 98—105.  .
• Crochemore, M., Lecroq, T., 1997, Tight bounds on the complexity of the Apostolico–Giancarlo algorithm, Information Processing Letters. . 63 (4): 195—203.  .
• Crochemore, M., Wojciech Rytter, 1994, Text Algorithms, Oxford University Press.
• Gusfield, D., 1997, Algorithms on strings, trees, and sequences: Computer Science and Computational Biology, Cambridge University Press.
• Lecroq, T., 1992, Recherches de mot, Ph. D. Thesis, University of Orléans, France.
• Lecroq, T., 1995, Experimental results on string matching algorithms, Software - Practice & Experience. . 25 (7): 727—765.  .