SELF-ALIGNMENTS IN WORDS AND THEIR APPLICATIONS

This paper deals with the probabilistic analysis of some quantitative measures associ-ated with periodicities in words, notably, the various values attained by the lengths of the longest common prefix of pairs of suffixes of a given word. Such values, that are called here self-alignments, playa crucial role in sever3J. algorithmic constructions, such as building the suffix tree or inverted file of a word, detecting squares and other repetitions in a word. computing substring statistics, etc. The probabilistic analysis of self-alignments is then used to study the expected time complexities of straightfor-ward algorithmic solutions to these problems, and to compare such performances with those attained by more complex constructions. Key words and phrases: Combinatorial algorithms on words, average case analysis of algo-rithms, Bemoulli model, self-alignments, periodicities in words. suffix trees, subsrring statistics