Finding the largest fixed-density necklace and Lyndon word

We present an O(n) time algorithm for finding the lexicographically largest fixed-density necklace of length n. Then we determine whether or not a given string can be extended to a fixed-density necklace of length n in O(n2) time. Finally, we give an O(n3) algorithm that finds the largest fixed-density necklace of length n that is less than or equal to a given string. The efficiency of the latter algorithm is a key component to allow fixed-density necklaces to be ranked efficiently. The results are extended to find the largest fixed-density Lyndon word of length n (that is less than or equal to a given string) in O(n3) time.