Computing maximal-exponent factors in an overlap-free word

The exponent of a word is the quotient of its length over its smallest period. The exponent and the period of a word can be computed in time proportional to the word length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free word. Our algorithm runs in linear-ti...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2016-05, Vol.82 (3), p.477-487
Main Authors: Badkobeh, Golnaz, Crochemore, Maxime
Format: Article
Language:English
Subjects:
Algorithm
Automaton
Computer Science
Data Structures and Algorithms
Periodicity
Power
Repeat
Repetition
Return word
String
Word
Word exponent
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The exponent of a word is the quotient of its length over its smallest period. The exponent and the period of a word can be computed in time proportional to the word length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free word. Our algorithm runs in linear-time on a fixed-size alphabet, while a naive solution of the question would run in cubic time. The solution for non-overlap-free words derives from algorithms to compute all maximal repetitions, also called runs, occurring in the word. We also show there is a linear number of occurrences of maximal-exponent factors in an overlap-free word. Their maximal number lies between 0.66n and 2.25n in a word of length n. The algorithm can additionally locate all of them in linear time.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2015.11.007