## Abstract

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.

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.

Original language | English |
---|---|

Pages (from-to) | 477-487 |

Number of pages | 11 |

Journal | JOURNAL OF COMPUTER AND SYSTEM SCIENCES |

Volume | 82 |

Issue number | 3 |

Early online date | 2 Dec 2015 |

DOIs | |

Publication status | Published - May 2016 |

## Keywords

- Algorithm
- Automaton
- Periodicity
- Power
- Repeat
- Repetition
- Return word
- String
- Word
- Word exponent