Apostolico-Giancarlo algorithm

The Apostolico-Giancarlo algorithm is a variant of the Boyer-Moore string-search algorithm, which looks for occurrences of a pattern in a longer text by aligning the pattern at an index of the text, checking for a match and then shifting the pattern by the Boyer-Moore rules. Apostolico-Giancarlo leaves the shift operation exactly as Boyer-Moore has it and changes only how a match at one alignment is checked. Plain Boyer-Moore must compare every character of the pattern explicitly, which is very inefficient for some inputs, for example when both pattern and text consist of one repeated character and the running time reaches O(nm). Apostolico-Giancarlo records in a table how many characters matched at earlier alignments of the text and combines that table with data gathered while preprocessing the pattern, so it can skip equality checks for sequences already known to match. It can be seen as a generalisation of the Galil rule.