Sequences and Digital Trees: A Symbiosis
Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1988
lbis paper studies in a probabilistic framework several topics concerning the ~ay words (slrings) can overlap.A word is defined as a random sequence of (possIble infinite) symbols over a V -ary alphabet A key notion of alignment (or.conuno~)where C~j is th~length of the .longest.Strin~tha~IS prefix of the i -lh and the j -th word.11us matnx plays a CruCial role In esll1Datmg some periodicities and correlations on words such as detecting squares and other repetitions, computing substring statistics.evaluating longest subs~ng common to a set of words, estimating the total length of a code needed to tranSmIt a set of wo~s.and so forth.On the other hand, the alignment mattix is a "bridge" between strIng characteristics and some parameters of digital trees built over these strings (e.g., radix tries, suffix trees, position trees, etc.).We explore this relationship and show how such a symbiosis can be used to evaluate expected complexity of string algorithms.