论文标题
相互边界和重叠
Mutual Borders and Overlaps
论文作者
论文摘要
如果一个单词是\ emph {bordered}，如果它包含一个也是后缀的非空置前缀。我们自然可以将此定义扩展到成对的非空词。如果存在一个单词$（u，v）$，则据说是\ emph {相互边界}，如果存在一个单词，一个单词是$ u $的非空正确前缀和$ v $的后缀，并且存在一个单词，一个单词是$ u $ u $ and preffix and $ v $ $ v $的非空格后缀。换句话说，如果$ u $叠加$ v $和$ v $叠加$ u $，则$（u，v）$相互边界。我们对相互边界对单词的数量进行了复发。此外，我们表明，渐近地表明，有$ c \ cdot k^{2n} $相互边界的长度 - $ n $上的$ k $ n $上的字母，其中$ c $是一个常数。最后，我们表明，对单词对之间的预期最短重叠在上面是常数。
A word is said to be \emph{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 \emph{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\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.
