Editing Boyer–Moore string-search algorithm (section)

==The Galil rule==
A simple but important optimization of Boyer–Moore was put forth by [[Zvi Galil]] in 1979.<ref name="galil">
{{cite journal
 | last1 = Galil | first1 = Z.
 | author1-link = Zvi Galil
 | title = On improving the worst case running time of the Boyer–Moore string matching algorithm
 | journal = Comm. ACM
 | volume = 22
 | issue = 9
 | pages = 505–508
 | publisher = Association for Computing Machinery
 | location = New York
 | date = September 1979
 | issn = 0001-0782
 | doi = 10.1145/359146.359148 | s2cid = 1333465
 | doi-access = free
 }}
</ref>
As opposed to shifting, the Galil rule deals with speeding up the actual comparisons done at each alignment by skipping sections that are known to match. Suppose that at an alignment {{math|''k''<sub>1</sub>}}, {{math|'''''P'''''}} is compared with {{math|'''''T'''''}} down to character {{math|'''''c'''''}} of {{math|'''''T'''''}}. Then if {{math|'''''P'''''}} is shifted to {{math|''k''<sub>2</sub>}} such that its left end is between {{math|'''''c'''''}} and {{math|''k''<sub>1</sub>}}, in the next comparison phase a prefix of {{math|'''''P'''''}} must match the substring {{math|'''''T'''''[(''k''<sub>2</sub> - ''n'')..''k''<sub>1</sub>]}}. Thus if the comparisons get down to position {{math|''k''<sub>1</sub>}} of {{math|'''''T'''''}}, an occurrence of {{math|'''''P'''''}} can be recorded without explicitly comparing past {{math|''k''<sub>1</sub>}}. In addition to increasing the efficiency of Boyer–Moore, the Galil rule is required for proving linear-time execution in the worst case.

The Galil rule, in its original version, is only effective for versions that output multiple matches. It updates the substring range only on {{math|1='''''c''''' = 0}}, i.e. a full match. A generalized version for dealing with submatches was reported in 1985 as the [[Apostolico–Giancarlo algorithm]].<ref>{{cite journal |last1=Apostolico |first1=Alberto |last2=Giancarlo |first2=Raffaele |title=The Boyer–Moore–Galil String Searching Strategies Revisited |journal=SIAM Journal on Computing |volume=15 |pages=98–105 |language=en |doi=10.1137/0215007 |date=February 1986|url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech |url-access=subscription }}</ref>