|
In [[computer science]], the '''Apostolico–Giancarlo algorithm''' is a variant of the [[Boyer–Moore string search algorithm]], the basic application of which is searching for occurrences of a pattern <math>P</math> in a text <math>T</math>. As with other comparison-based string searches, this is done by aligning <math>P</math> to a certain index of <math>T</math> and checking whether a match occurs at that index. <math>P</math> is then shifted relative to <math>T</math> according to the rules of the Boyer-MooreBoyer–Moore algorithm, and the process repeats until the end of <math>T</math> has been reached. Application of the Boyer-Moore shift rules often results in large chunks of the text being skipped entirely.
With regard to the shift operation, Apostolico-GiancarloApostolico–Giancarlo is exactly equivalent in functionality to Boyer-MooreBoyer–Moore. The utility of Apostolico-GiancarloApostolico–Giancarlo is to speed up the match-checking operation at any index. With Boyer-Moore, finding an occurrence of <math>P</math> in <math>T</math> requires that all <math>n</math> characters of <math>P</math> be explicitly matched. For certain patterns and texts, this is very inefficient -– a simple example is when both pattern and text consist of the same repeated character, in which case Boyer-MooreBoyer–Moore runs in <math>O(n m)</math>, where <math>m</math> is the length in characters of <math>T</math>. Apostolico-GiancarloApostolico–Giancarlo speeds this up by recording the number of characters matched at the alignments of <math>T</math> in a table, which is combined with data gathered during the pre-processing of <math>P</math> to avoid redundant equality checking for sequences of characters that are known to match.
==References==
* Apostolico A., Giancarlo R., 1986, The Boyer-Moore-GalilBoyer–Moore–Galil string searching strategies revisited, [[SIAM Journal on Computing]] 15(1):98-10598–105. [[Digital Object Identifier{{doi|doi]]: [https://dx.doi.org/10.1137/0215007 10.1137/0215007]}}.
* Crochemore, M., Lecroq, T., 1997, Tight bounds on the complexity of the Apostolico–Giancarlo algorithm, Information Processing Letters 63(4):195-203195–203. [[Digital Object Identifier{{doi|doi]]: [https://dx.doi.org/10.1016/S0020-0190(97)00107-5 10.1016/S0020-0190(97)00107-5]}}.
* Crochemore, M., [[Wojciech Rytter|Rytter, W.]], 1994, Text Algorithms, [[Oxford University Press]].
* Gusfield, D., 1997, Algorithms on strings, trees, and sequences: Computer Science and Computational Biology, [[Cambridge University Press]]. {{ISBN|0-521-58519-8}}.
* Lecroq, T., 1992, Recherches de mot, Ph. D. Thesis, [[Orléans|University of Orléans]], France.
* Lecroq, T., 1995, Experimental results on [[String searching algorithm|string matching]] algorithms, Software -– Practice & Experience 25(7):727-765727–765. [[Digital Object Identifier{{doi|doi]]: [https://dx.doi.org/10.1002/spe.4380250703 10.1002/spe.4380250703]}}.
{{Strings}}
|
