Mutual Borders and Overlaps
Daniel Gabrić · IEEE Transactions on Information Theory · 2022
A word is said to beborderedif 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 bemutually borderedif 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\cdot 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.