NIST

Two Way algorithm

(algorithm)

Definition: Partition ("factor") the pattern, x, into left, xl, and right, xr, parts in such a way to optimize searching. Compare xr left to right then, if it matches, compare xl right to left.

Generalization (I am a kind of ...)
string matching algorithm.

See also Knuth-Morris-Pratt algorithm, Boyer-Moore.

Note: [It] "can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt on the one hand and Boyer and Moore, on the other hand."

Author: PEB

Implementation

Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)

More information

Maxime Crochemore and Dominique Perrin, Two-way string-matching, Journal of the ACM, 38(3):651-675, July 1991.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 February 2005.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "Two Way algorithm", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/twoWay.html