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

Regnier, Mireille

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

Keywords:

string matching; average analysis; combinatorics on words; generating functions

Citations:

Zbl 0726.00018; Zbl 0372.68005