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