🚀 go-pugleaf

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

DATA STRUCTURES SEMINAR

                    -Monday, May 29, 1989

Professor  Mireille  R`gnier, INRIA, France, will speak on
"An   Algebraic   Analysis  of  the  Knuth-Morris-Pratt
Algorithm."

TIME:                 3:30 p.m.

ROOM:              DC 1304

ABSTRACT

We  present  an  average  analysis  of  a basic string-
searching  algorithm: the Knuth-Morris-Pratt algorithm.
We  consider  the  number  of  text-pattern comparisons
performed  when searching a pattern  p in a text  t  of
length  n.  It is known to be   O(n).  We show that for
a  given pattern  p and a random text  t,  this cost is
asymptotically   c  subscript p  n.  Averaging over all
possible patterns  p  yields a constant of linearity  c.
When  the cardinality  q  of the alphabet is large,
it is proven that
c approximates  1 + 1 over q .  An algebraic scheme is
used,  based  on  combinatorics on words and generating
functions.   First, the problem is reduced to a problem
of   word   enumeration.    Then,  known  results  from
combinatorics   of   words   apply,   which  allow  the
computation of the associated generating functions.