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."
Maxime Crochemore and Dominique Perrin, Two-way string-matching, Journal of the ACM, 38(3):651-675, July 1991.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 2 February 2005.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Paul E. Black, "Two Way algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 2 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/twoWay.html