DOIAbstract
AbstractA few lines pattern matching algorithm is obtained by using the correctness proof of programs as a tool to the design of efficient algorithms. The new algorithm is obtained from a brute force algorithm by three refinement steps. The first step leads to the algorithm of Knuth, Morris, and Pratt that performs 2n character comparisons in the worst case and (1 + α)n comparisons in the average case (0<α≤0.5). Two more steps give a faster algorithm that performs 1.5n character comparisons in the worst case and is sublinear on a random text for all patterns. Moreover, those bounds are less than the corresponding bounds of the Boyer and Moore algorithm because the Boyer and Moore algorithm performs more than 2n character comparisons in the ...
Add to ORKG