Burrows–Wheeler Transform (BWT，块排序压缩 )
可爱即是正义
·
2022-04-18 00:26:37
·
个人记录
Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），主要应用于数据压缩领域
来源于一道题 Timus1322 Spy
大意是给出一个长度为n的串c，只含大小写字母和下划线的串，并把这个串 串尾的字母放到串首，直到生成n个串。首字母为c_i的串编号为i。并对这n个串按字典序排序，生成一个nxn的字符矩阵。
现给出该矩阵的最后一列和最后一行字符串的编号。求出原始串。
待更 先放这么一段英文的在这里
By the help of ind array,we can use n=ind[n] to access all sorted string,step by step,such as from S_2 to S_3,S_4..... S_N until S_0.
Because all string is build by the same way so we can use ind array to rebuild all string
So we need to build such array. First we should sort all character in last column.and for each sorted character we can find a origin character in last column. So the ind array is built because S_ns last character is same as S_n+1s first character.