## Knuth-Morris-Pratt algorithm: An analysis.(English)Zbl 0755.68074

Mathematical foundations of computer science, Proc. 14th Symp., MFCS ’89, Porąbka-Kozubnik/Pol. 1989, Lect. Notes Comput. Sci. 379, 431-444 (1989).
Summary: [For the entire collection see Zbl 0726.00018.]
This paper deals with an average analysis of the Knuth-Morris-Pratt algorithm [D. E. Knuth, J. H. Morris and V. R. Pratt [SIAM J. Computing 6, 323-350 (1977; Zbl 0372.68005)]. Searching all occurrences of a given pattern $$p$$ in a text of length $$n$$ implies $$c_ p.n$$ text-pattern comparisons. Averaging over all patterns yields a cost $$c.n$$. The constant of linearity $$c$$ is derived. In particular, when the cardinality $$q$$ of the alphabet is large, it is proven that $$c\sim 1+{1\over q}$$. An algebraic scheme is used, based on combinatorics on words and generating functions.

### MSC:

 68Q25 Analysis of algorithms and problem complexity

### Citations:

Zbl 0726.00018; Zbl 0372.68005