Computing maximal-exponent factors in an overlap-free word

Golnaz Badkobeh; Maxime Crochemore

doi:10.1016/j.jcss.2015.11.007

Computing maximal-exponent factors in an overlap-free word

Golnaz Badkobeh, Maxime Crochemore^*

^*Corresponding author for this work

Informatics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

142 Downloads (Pure)

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.

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	https://doi.org/10.1016/j.jcss.2015.11.007
Publication status	Published - May 2016

Keywords

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

Access to Document

10.1016/j.jcss.2015.11.007

Computing maximal-exponent factors_BADKOBEH_Accepted27August2014_GREEN AAM (CC BY-NC-ND)
© <2016> This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
Accepted author manuscript, 210 KBLicence: CC BY-NC-ND

Cite this

@article{67dc946b7ae24edd931b28066b6b8a95,

title = "Computing maximal-exponent factors in an overlap-free word",

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.",

keywords = "Algorithm, Automaton, Periodicity, Power, Repeat, Repetition, Return word, String, Word, Word exponent",

author = "Golnaz Badkobeh and Maxime Crochemore",

year = "2016",

month = may,

doi = "10.1016/j.jcss.2015.11.007",

language = "English",

volume = "82",

pages = "477--487",

journal = "JOURNAL OF COMPUTER AND SYSTEM SCIENCES",

issn = "0022-0000",

publisher = "ACADEMIC PRESS INC",

number = "3",

}

TY - JOUR

T1 - Computing maximal-exponent factors in an overlap-free word

AU - Badkobeh, Golnaz

AU - Crochemore, Maxime

PY - 2016/5

Y1 - 2016/5

N2 - 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.

AB - 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.

KW - Algorithm

KW - Automaton

KW - Periodicity

KW - Power

KW - Repeat

KW - Repetition

KW - Return word

KW - String

KW - Word

KW - Word exponent

UR - http://www.scopus.com/inward/record.url?scp=84950259541&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2015.11.007

DO - 10.1016/j.jcss.2015.11.007

M3 - Article

AN - SCOPUS:84950259541

SN - 0022-0000

VL - 82

SP - 477

EP - 487

JO - JOURNAL OF COMPUTER AND SYSTEM SCIENCES

JF - JOURNAL OF COMPUTER AND SYSTEM SCIENCES

IS - 3

ER -

Computing maximal-exponent factors in an overlap-free word

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this