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 ⌈log2(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 + ⌊(1⁄2 + ε)(n − m)⌋ comparisons, with ε = (u,v)⁠ of a string x. For example, ("Wiki","pedia") is a factorization of "Wikipedia".
• A period of a string p-distance apart are equal. More precisely, n has a period of ⁠⁠u or w is a prefix of w;

In other words, ⁠(u,v)⁠ is denoted as vu is guaranteed to exist and has the same length as 1≤r(u,v)≤len(x)⁠.

Finally, a critical factorization is a factorization x such that m in an ordered alphabet, it can be computed in Charras, Christian; Lecroq, Thierry (14 January 1997). "Two Way algorithm". Exact String Matching Algorithms. Institut Gaspard Monge.

↑ "newlib/libc/string/memmem.c". Retrieved 23 November 2019.

1 2 Adamczyk, Zbigniew; Rytter, Wojciech (May 2013). "A note on a simple computation of the maximal suffix of a string" (PDF). Journal of Discrete Algorithms. 20: 61–64. doi:10.1016/j.jda.2013.03.002.

• Approximate string matching
• Bitap algorithm
• Damerau–Levenshtein distance
• Edit distance
• Gestalt pattern matching
• Hamming distance
• Jaro–Winkler distance
• Lee distance
• Levenshtein automaton
• Levenshtein distance
• Wagner–Fischer algorithm

• Apostolico–Giancarlo algorithm
• Boyer–Moore string-search algorithm
• Boyer–Moore–Horspool algorithm
• Knuth–Morris–Pratt algorithm
• Rabin–Karp algorithm
• Raita algorithm
• Trigram search
• Two-way string-matching algorithm
• Zhu–Takaoka string matching algorithm

• Aho–Corasick
• Commentz-Walter algorithm

• Comparison of regular-expression engines
• Regular grammar
• Thompson's construction
• Nondeterministic finite automaton

• BLAST
• Hirschberg's algorithm
• Needleman–Wunsch algorithm
• Smith–Waterman algorithm

• DAFSA
• Substring index
  • Suffix array
  • Suffix automaton
  • Suffix tree
  • Compressed suffix array
  • LCP array
  • FM-index
• Generalized suffix tree
• Rope
• Ternary search tree
• Trie

• Parsing
• Pattern matching
• Compressed pattern matching
• Longest common subsequence
• Longest common substring
• Sequential pattern mining
• Sorting
• String rewriting systems
• String operations