A well-known algorithm that performs this task, which is not branching, uses two structures informally known as "jump tables", the first of which is not used in a modification of that algorithm partially named for Horspool.
A well-known algorithm that performs this task, which is not branching, uses two structures informally known as "jump tables", the first of which is not used in a modification of that algorithm partially named for Horspool. A trie ("try") with suffix-tree-like links between its nodes is constructed by another algorithm to perform this task; that algorithm is the Aho-Corasick algorithm. This operation, performed by the aforementioned backwards- working Boyer-Moore algorithm, is also performed by an algorithm built around a (*) rolling hash, though that algorithm is less efficient than one that includes a "failure function" to avoid checking characters multiple times, the Knuth-Morris-Pratt algorithm. For 10 points, name this operation that is performed by the Rabin-Karp algorithm and the Unix utility grep, which in general involves finding an item, often a string.
A well-known algorithm that performs this task, which is not branching, uses two structures informally known as "jump tables", the first of which is not used in a modification of that algorithm partially named for Horspool.
{searching} [or {pattern matching}; accept {more specific} answers, {such} as {array} or {string searching} or {string matching}, etc.; accept {logical} equivalents {such} as {locating substrings within strings}, etc.]