語のLyndon判定アルゴリズム

語のDuval分解アルゴリズム

0. 語を用意する
1. 語について非Lyndonと仮定しておく
2. 語をどこかで二つに分ける
3. 手前と後の語を辞書式に比較する
4. 手前の方が小さいなら、2.から順に繰り返す(別の場所で区切る)
5. 手前の方が大きいなら、分けた二つの語について、1.から順に繰り返す
6. ある語について4.をすべての区切りで試して必ず手前の方が小さいなら、分けられた残りの語について2.から順に繰り返す(この語がLyndon)
7. 5.で分けたすべての語(*葉ノード)について6.でLyndonと判定されたとき、アルゴリズムを終了する(葉ノード以外の語はすべて非Lyndon)
   分けられない語はLyndon