The Distribution of Prefix Overlap in Consecutive Dictionary Entries
Rodica E. Simion, Herbert S. Wilf · SIAM Journal on Algebraic and Discrete Methods · 1986
We consider the family $\Delta ( m;\mathcal{A} )$ of all dictionaries, over an alphabet $\mathcal{A}$, that have given numbers $m_i $ of words of each length $i = 1,2, \cdots $ . We find the probability distribution of the length of the maximal common prefix of two consecutive words in dictionaries $\mathcal{D} \in \Delta $, and the asymptotic behavior of the average length of those common prefixes. In the case of dictionaries of D words, all of the same length, the size of the average prefix overlap is “near” $\log _A D ( A = | \mathcal{A} | )$.