BWTとSAの関係
BWTと接尾辞配列の関係
接尾辞$ T[i..n] ではなくサイクリックシフト$ T[i..n]T[0..i-1] をソートしたものを考える
どちらをソートしても順番は同じ
SA
整数の配列
サイクリックシフトのテキスト中での開始位置を意味する
BWT
文字の配列
サイクリックシフトの末尾の文字Lを意味する
サイクリックシフトの先頭Fはソートされているので、この配列をソートすることで得られる
LからFへの対応づけを構築できて、ここからテキストの再構築ができる