 in computer science, the boyerâmoore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature.hume and sunday (1991) [fast string searching] softwareâpractice and experience, vol. 21(11), 1221â1248 (november 1991) it was developed by robert s. boyer and j strother moore in 1977.  the algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). it is thus well-suited for applications in which the pattern is much shorter than the text or does persist across multiple searches. the boyer-moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string algorithms. in general, the algorithm runs faster as the pattern length increases. the key feature of the algorithm is to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text. ==definitions== {| | a||n||p||a||n||m||a||n||- |- | p||a||n||-||-||-||-||-||- |- | -||p||a||n||-||-||-||-||- |- | -||-||p||a||n||-||-||-||- |- | -||-||-||p||a||n||-||-||- |- | -||-||-||-||p||a||n||-||- |- | -||-||-||-||-||p||a||n||- |} alignments of pattern pan to text anpanman, from k=3 to k=8. a match occurs at k=5. * s[i] refers to the character at index i of string s, counting from 1. * s[i..j] refers to the substring of string s starting at index i and ending at j, inclusive. * a prefix of s is a substring s[1..i] for some i in range [1, n], where n is the length of s. * a suffix of s is a substring s[i..n] for some i in range [1, n], where n is the length of s. * the string to be searched for is called the pattern and is referred to with symbol p. * the string being searched in is called the text and is referred to with symbol t. * the length of p is n. * the length of t is m. * an alignment of p to t is an index k in
Algorithms_on_strings String_matching_algorithms