Two-way string-matching algorithm

In computer science, the two-way string-matching algorithm (or Crochemore-Perrin string-matching algorithm) is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. It searches for copies of a "needle" of length m in a "haystack" of length n. After preprocessing the needle in time O(m), the actual search takes time O(n) linear in the length of the haystack. The two-way algorithm can be viewed as a combination of the forward-going Knuth–Morris–Pratt algorithm (KMP) and the backward-running Boyer–Moore string-search algorithm (BM). Like those two, the two-way algorithm preprocesses the needle to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered. Unlike BM and KMP, it uses only O(1) additional space to store information about those partial repeats (assuming the transdichotomous model, where an index of ⌈log 2 (m)⌉ bits is counted as a single word). The preprocessing computes the "period" of the needle, the minimum offset between two consecutive matches (a value between 1 and m), and a "critical factorization" of the needle into a prefix and suffix with particular properties, specified by the length of the prefix (also less than m). The actual matching operation performs at most 2n − m comparisons.…

In computer science, the two-way string-matching algorithm (or Crochemore-Perrin string-matching algorithm) is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. It searches for copies of a "needle" of length m in a "haystack" of length n. After preprocessing the needle in time O(m), the actual search takes time O(n) linear in the length of the haystack. The two-way algorithm can be viewed as a combination of the forward-going Knuth–Morris–Pratt algorithm (KMP) and the backward-running Boyer–Moore string-search algorithm (BM). Like those two, the two-way algorithm preprocesses the needle to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered. Unlike BM and KMP, it uses only O(1) additional space to store information about those partial repeats (assuming the transdichotomous model, where an index of ⌈log 2 (m)⌉ bits is counted as a single word). The preprocessing computes the "period" of the needle, the minimum offset between two consecutive matches (a value between 1 and m), and a "critical factorization" of the needle into a prefix and suffix with particular properties, specified by the length of the prefix (also less than m). The actual matching operation performs at most 2n − m comparisons. Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle: The first one performs at most n + ⌊(n − m)/2⌋ comparisons, ⌈(n − m)/2⌉ fewer than the original. It must however store ⌈log φ m⌉ additional offsets into the needle. The second adapts it to only store a constant number of such offsets, denoted c, but must perform n + ⌊( + ε)(n − m)⌋ comparisons, with ε = (F c+2 − 1) −1 ∈ O(φ −c ) going to zero exponentially quickly as c increases. The algorithm is considered fairly efficient in practice, being cache-friendly and using several operations that can be implemented in well-optimized subroutines. It is used by the C standard libraries glibc, newlib, and musl, to implement the memmem and strstr family of substring functions. As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances; this is especially so if the needle isn't searched in multiple haystacks, which would amortize the preprocessing cost. if a = b return 0 if a idx2 return [idx1, per1] else return [idx2, per2] The comparison proceeds by first matching for the right-hand-side, and then for the left-hand-side if it matches. Linear-time skipping is done using the period. function match(needle, haystack) needle_len ← len(needle) haystack_len ← len(haystack) [length, cur_period] ← crit_fact(needle) Matches ← {} set of matches. Match the suffix. Use a library function like memcmp, or write your own loop. if needle[0] ... needle[length] == needle[length + 1] ... needle[length + cur_period] Matches ← {} pos ← 0 s ← 0 TODO. At least put the skip in.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372977915 under CC BY-SA 4.0; modifications have been made.