摘要: This paper deals with an average analysis of the Knuth-Morris-Pratt algorithm. Searching all occurrences a given pattern p in text length n implies cp.n text-pattern comparisons. Averaging over patterns yields cost c.n. The constant linearity c is derived. In particular, when cardinality q alphabet large, it proven that ∼ 1+1/q. An algebraic scheme used, based on combinatorics words and generating functions.
springer.com
springerlink.com参考文章(6)
M. Lothaire, Combinatorics on Words ,(1984)
Philippe Flajolet, Elements of a general theory of combinatorial structures fundamentals of computation theory. pp. 112- 127 ,(1985) , 10.1007/BFB0028797
Alfred V. Aho, Pattern Matching in Strings Formal Language Theory#R##N#Perspectives and Open Problems. pp. 325- 347 ,(1980) , 10.1016/B978-0-12-115350-2.50016-6
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
L.J Guibas, A.M Odlyzko, String overlaps, pattern matching, and nontransitive games Journal of Combinatorial Theory, Series A. ,vol. 30, pp. 183- 208 ,(1981) , 10.1016/0097-3165(81)90005-4
Leo J. Guibas, Periodicities in Strings Springer, Berlin, Heidelberg. pp. 257- 269 ,(1985) , 10.1007/978-3-642-82456-2_17