Editing Boyer–Moore string-search algorithm (section)

==Performance==
The Boyer–Moore algorithm as presented in the original paper has worst-case running time of {{tmath|O(n+m)}} only if the pattern does ''not'' appear in the text. This was first proved by [[Donald Knuth|Knuth]], [[James H. Morris|Morris]], and [[Vaughan Pratt|Pratt]] in 1977,<ref name="Knuth_Morris_Pratt" /> followed by [[Leonidas J. Guibas|Guibas]] and [[Andrew Odlyzko|Odlyzko]] in 1980<ref name="go">
{{cite journal
 | last1 = Guibas | first1 = Leonidas
 | author1-link = Leonidas J. Guibas
 | last2 = Odlyzko | first2 = Andrew
 | author2-link = Andrew Odlyzko
 | title = A new proof of the linearity of the Boyer–Moore string searching algorithm
 | journal = Proceedings of the 18th Annual Symposium on Foundations of Computer Science
 | series = SFCS '77
 | pages = 189–195
 | publisher = IEEE Computer Society
 | location = Washington, District of Columbia
 | year = 1977
 | url = http://dl.acm.org/citation.cfm?id=1382431.1382552
 | doi = 10.1109/SFCS.1977.3 | s2cid = 6470193
 | url-access = subscription
 }}
</ref> with an upper bound of {{math|5''n''}} comparisons in the worst case. [[Richard J. Cole|Richard Cole]] gave a proof with an upper bound of {{math|3''n''}} comparisons in the worst case in 1991.<ref name="cole">
{{cite journal
 | last1 = Cole | first1 = Richard
 | title = Tight bounds on the complexity of the Boyer–Moore string matching algorithm
 | journal = Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms
 | series = Soda '91
 | pages = 224–233
 | publisher = Society for Industrial and Applied Mathematics
 | location = Philadelphia, Pennsylvania
 | date = September 1991
 | url = http://dl.acm.org/citation.cfm?id=127830
 | isbn = 0-89791-376-0 }}
</ref>

When the pattern ''does'' occur in the text, running time of the original algorithm is {{tmath|O(nm)}} in the worst case. This is easy to see when both pattern and text consist solely of the same repeated character. However, inclusion of the [[Galil rule]] results in linear runtime across all cases.<ref name="galil" /><ref name="cole" />