Article ID Journal Published Year Pages File Type
434475 Theoretical Computer Science 2014 8 Pages PDF
Abstract

We present an algorithm that, given a word w of length n   on an unordered alphabet, computes one of its unbordered conjugates. If such a conjugate does not exist, the algorithm computes one of its conjugates that is a power of an unbordered word. The time complexity of the algorithm is O(n)O(n): the number of comparisons between letters of w is bounded by 4n.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Linear computation of unbordered conjugate on unordered alphabet
Authors
, , ,