## 語のLyndon判定アルゴリズム

start=>start
: 語がLyndonか判定する
input: 語
word_io=>inputoutput: 語
cut=>operation: 2つの語に分ける
compare_words=>condition
: Yes or No?
手前の語が
後の語より大きい

start->word_io->cut->compare_words

other_cut_exists=>condition
: Yes or No?
他に試していない
2つの語に分ける
場所がある

is_lyndon=>end
: indputの語はLyndon
output: Lyndonフラグ

compare_words(no)->other_cut_exists(yes)->cut

lyndon_flag_out=>inputoutput: Lyndon語フラグ

other_cut_exists(no)->lyndon_flag_out->is_lyndon

not_lyndon=>end
: inputの語はLyndonではない
output: 非Lyndonフラグと
2つの分けられた語

two_words_out=>inputoutput
: 非Lyndonフラグと
2つの語

compare_words(yes)->two_words_out->not_lyndon

## 語のDuval分解アルゴリズム

start=>start
: 語をDuval分解した二分木を作成する
input: 語
word_io=>inputoutput: 語
make_leaf=>operation
: 語を二分木の葉の子に置く
親がなければ親になる
choose_leaf=>operation: 葉のうちLyndonでない語を選ぶ
is_lyndon=>condition: Lyndon判定

start->word_io->make_leaf->choose_leaf->is_lyndon

make_binary=>parallel: 葉の子に、分けた順に2つの語をつける

is_lyndon(no)->make_binary

make_binary(path1, top)->make_leaf
make_binary(path2, right)->make_leaf
lyndon_leaf=>operation: 葉をLyndonとする
lyndon_or_not=>condition: 葉はすべてLyndonか


is_lyndon(yes)->lyndon_leaf->lyndon_or_not
lyndon_or_not(no)->choose_leaf

binary_io=>inputoutput: Duval分解二分木

end=>end
: Duval分解完了
output: Duval分解済みの二分木

lyndon_or_not(yes)->binary_io->end

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