Two-way string-matching

Publisher Website
Google Scholar
Abstract
A new string-matching algorithm is presented, which 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. The algorithm is linear in time and uses constant space as the algorithm of Galil and Seiferas. It presents the advantage of being remarkably simple which consequently makes its analysis possible. The algorithm relies on a previously known result in combinatorics on words, called the Critical Factorization Theorem,which relates the global period of a word to Its local repetitions of blocks

This publication has 20 references indexed in Scilit: