特に断りがない場合、文字列の長さを $n$で表す。
文字列は 0-indexed であり、文字列 $\lambda$ の $i$ 文字目を $\lambda_i$ で、 $l$ 文字目から $r-1$ 文字目の部分文字列を $\lambda_{[l,r)}$ で表す。
文字列の順序を一般的な辞書順で考える。 辞書順で考える都合上、場合分けをなくすため断りなく文字列の末尾に最小文字が入っているとみなす場合がある。
文字列 $\lambda$ が Lyndon文字列 であるとは、 $\lambda$ の空文字列でない任意の真の接尾辞より $\lambda$ の辞書式順序が小さいことである。
すなわち、任意の $k\in(0,n)$ について $\lambda <\lambda_{[k,n)}$ が成り立つことである。
文字列 $\lambda$ が Lyndon文字列 であるとは、 $\lambda$ の任意の真の循環文字列より $\lambda$ の辞書式順序が小さいことである。
すなわち、任意の $k>0$ について $\lambda <\lambda_{[k,n)}\lambda_{[0,k)}$ が成り立つことである。
例
ababb: Lyndon文字列
abbaba: Lyndon文字列ではない
定義1と定義2は同値である。
証明