The simple string-matching algorithm presented here uses the critical factorization theorem. First, the pattern x is factored into x = x l x r by a critical position l (shown to reduce to the computation of the maximal suffix of x) and the period of the pattern is computed.
The string-matching algorithm itself has two phases. The first phase of the algorithm compares x r with the text, scanning from left to right. If a mismatch is found in this phase, then the pattern is shifted right by l. If no mismatch occurs, then the second phase of the algorithm compares x l with the text, scanning from right to left. If a mismatch occurs, then the pattern is shifted by the period of the pattern. This two-way string-matching algorithm uses linear time and constant space, which compares with the well-known Knuth-Morris-Pratt and Boyer-Moore algorithms.
The paper is well written. The algorithms are described simply, and proofs of termination and correctness are accompanied by many diagrams that help illustrate both how the algorithm works and what the variables in the algorithm represent.