An ordered alphabet Σ is a set of symbols {σ₁, σ₂,...,σ_ℓ} such that σ₁ < σ₂ < ... < σ_ℓ.

A word w = w₀w₁..w_n-1 of length |w| = n on alphabet Σ is the concatenation of n symbols w_k (0 ≤ k < n) drawn from Σ. The empty word of length 0 is denoted by ε.

Given a word w, if w can be written as the concatenation of three possibly empty words u, v and z (w = uvz), then:

• u is called a prefix of w
• v is called a factor of w
• z is called a suffix of w

A prefix, factor or suffix is said to be proper iff it is different from w itself.

The set of all the prefixes (resp. factors, suffixes) of a word w is denoted by Pref(w) (resp. Fact(w), Suf(w)).

The prefix (resp. suffix) of length k of a word w is denoted by Pref_k(w) (resp. Suf_k(w)).

Given a word w, any word in Pref(w) ∩ Suf(w) is called a border of w. The set of all the borders of w is denoted by Bord(w).

A word w of length n has period p, 0 < p < n, iff, ∀ 0 ≤ k < n - p, w_k = w_k+p.

If no such period exists, the word is said to be aperiodic.

A word is primitive iff there does not exist any p < n dividing n such that p is a period of w.

If a word w can be written as the concatenation of two words u and v (w = uv), then the word vu is called a conjugate of w.

The set of all the conjugates of a word w is denoted by Conj(w) and is called the conjugacy class of w.

The lexicographic order <_lex (lexorder for short) is defined as follows. Given two words w and w' on an ordered alphabet Σ, then w < _lex w' iff one of these conditions is verified:

• w is a proper prefix of w'
• ∃ k ≥ 0 such that Pref_k(w) = Pref_k(w') and w_k < w'_k

A word is a Lyndon word iff it is strictly less (in lexorder) than any of its proper suffixes.

Example:

• ananas is a Lyndon word since ananas <_lex anas <_lex as <_lex nanas <_lex nas <_lex s
• banana is not a Lyndon word since a <_lex ana <_lex anana <_lex banana <_lex na <_lex nana

A word is a Lyndon word iff it is the only smallest (in lexorder) element of its conjugacy class.

Example:

• ananas is a Lyndon word since ananas <_lex anasan <_lex asanan <_lex nanasa <_lex nasana <_lex sanana
• banana is not a Lyndon word since abanan <_lex anaban <_lex ananab <_lex banana <_lex nabana <_lex nanaba

A word w of length n is a Lyndon word iff ∀ 0 < k < n, Pref_k(w) <_lex Suf_k(w).

Example:

• ananas is a Lyndon word since a <_lex s, an<_lex as, ana <_lex nas, anan <_lex anas, anana <_lex nanas
• banana is not a Lyndon word since a <_lex b...

Given a word w of length n, the Lyndon array of w, denoted by L_w is defined as: ∀ 0 ≤ k < n, L_w[k] is the length of the longest prefix of w_k..w_n-1 that is a Lyndon word.

Example: