Mutual Borders and Overlaps

10/27/2020

∙

by   Daniel Gabric, et al.

∙

0

∙

share

A word is said to be bordered if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words (u,v) is said to be mutually bordered if there exists a word that is a non-empty proper prefix of u and suffix of v, and there exists a word that is a non-empty proper suffix of u and prefix of v. In other words, (u,v) is mutually bordered if u overlaps v and v overlaps u. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are c· k^2n mutually bordered words of length-n over a k-letter alphabet, where c is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant.