
























A \emph{border} of a word $w$ is a word that is both a non-empty proper prefix and suffix of $w$. If $w$ has a border, then it is said to be \emph{bordered}; otherwise, it is said to be \emph{unbordered}. The main results of this paper are the first algorithms to rank and unrank length-$n$ bordered and unbordered words over a $k$-letter alphabet. We show that, under the unit-cost RAM model, ranking bordered and unbordered words can be done in $O(kn^3)$ time using $O(n)$ space, and unranking them can be done in $O(n^4k\log k)$ time using $O(n)$ space.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。