Apostolico–Giancarlo algorithm: Difference between revisions

Revision as of 17:51, 2 April 2012

Revision as of 03:25, 3 June 2012

Line 1:

{{context|date=December 2011}}

{{Lead rewrite|date=September 2009}}

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-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.