Dictionnaire

この位置の文字をBWT系列の文字列「ccoaa」から順番に取り出すと「cacao」となり、元の文字列が得られる。 ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えばクイックソートなど)を単純に適用すると文字列の長さ n {\displaystyle n} に対して O ( n 2