题目描述本题要求实现Burrows–Wheeler\texttt{Burrows–Wheeler}Burrows–Wheeler变换BWT\texttt{BWT}BWT。给定一个长度为NNN的字符串SSS首先生成它的NNN个循环移位字符串S0,S1,…,SN−1S_0, S_1, \dots, S_{N-1}S0​,S1​,…,SN−1​其中S0SS_0 SS0​SSkS_kSk​由Sk−1S_{k-1}Sk−1​将第一个字符移动到末尾得到。然后将这NNN个字符串按字典序排序输出排序后矩阵的最后一列所组成的字符串以及S1S_1S1​即原串左移一位在排序后的行号从000开始。输入中字符串可能跨多行每行除最后一行外恰好505050个字符。输出时最后一列字符串也按每行505050个字符最后一行可少于505050输出。输入格式第一行为一个整数MMM表示数据集的个数。随后可能有一个空行。每个数据集的第一行为整数NNNN1997N 1997N1997表示字符串长度。接下来若干行包含该字符串每行除最后一行外恰好505050个字符。数据集之间可能有一个空行。输出格式对于每个数据集输出两行或更多第一行输出S1S_1S1​在排序后数组中的行号从000开始计数。随后若干行输出变换后的最后一列字符串每行最多505050个字符。每组输出之间用一个空行分隔。样例输入1 6 pascal输出1 cpsala题目分析Burrows–Wheeler\texttt{Burrows–Wheeler}Burrows–Wheeler变换是数据压缩中的经典预处理步骤它通过重排字符使得具有相同上下文的字符聚集便于后续压缩。本题要求实现最基本的变换过程构造所有循环移位共NNN个。按字典序排序这些移位。提取排序后每个字符串的最后一个字符拼接成新字符串。输出原串S1S_1S1​即原串左移一位所在的行号。由于NNN最大仅为199719971997直接生成所有移位并排序是完全可行的。字符串的存储和比较均为O(N)O(N)O(N)总复杂度约为O(N2log⁡N)O(N^2 \log N)O(N2logN)在给定数据范围内可以接受。解题思路读取字符串由于输入中字符串可能被分割成多行每行除最后一行外恰好505050个字符我们需要连续读取行直至累积长度达到NNN然后将多余字符丢弃但题目保证不会多出。生成循环移位设原串为word长度为NNN。初始化一个向量words每个元素包含一个整数label表示该串是由原串循环左移label位得到和一个字符串s当前的循环移位。第000个循环移位即为word。对于iii从111到N−1N-1N−1将当前串的第一个字符移到末尾得到下一个移位并存入向量。排序使用stable_sort\texttt{stable\_sort}stable_sort按字符串字典序升序排序。由于label可以唯一标识原串的偏移即使字符串相同理论上可能重复也不会影响排序稳定性但这里使用稳定排序是为了保持原始顺序实际上并不影响最终结果。提取最后一列和行号遍历排序后的向量words将每个字符串的最后一个字符s.back()拼接到结果字符串created中。若当前label 1则记录当前下标indexer即为S1S_1S1​所在行号。输出先输出indexer然后按每行505050个字符输出created。复杂度分析生成NNN个循环移位每个字符串长度为NNN总时间复杂度为O(N2)O(N^2)O(N2)。排序比较字符串O(Nlog⁡N)O(N \log N)O(NlogN)次每次比较最坏O(N)O(N)O(N)故排序部分O(N2log⁡N)O(N^2 \log N)O(N2logN)。总体时间复杂度为O(N2log⁡N)O(N^2 \log N)O(N2logN)当N1997N 1997N1997时约为4×106×11≈4.4×1074 \times 10^6 \times 11 \approx 4.4 \times 10^74×106×11≈4.4×107次字符比较在可接受范围内。空间复杂度为O(N2)O(N^2)O(N2)用于存储所有循环移位字符串。代码实现// Compression (II)// UVa ID: 632// Verdict: Accepted// Submission Date: 2016-08-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structcell{intlabel;string s;booloperator(constcellanother)const{returnsanother.s;}};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intdatasets;cindatasets;string line;for(intd1;ddatasets;d){if(d1)cout\n;intlength;cinlength;cin.ignore(1024,\n);string word;while(true){getline(cin,line);wordline;if(word.length()length)break;}string s0word,s1word;s1.push_back(s1.front());s1.erase(s1.begin());vectorcellwords;for(inti0;ilength;i){words.push_back((cell){i,word});word.push_back(word.front());word.erase(word.begin());}stable_sort(words.begin(),words.end());string created;intindexer-1;for(inti0;ilength;i){createdwords[i].s.back();if(indexer-1words[i].label1)indexeri;}coutindexer\n;while(created.length()50){coutcreated.substr(0,50)\n;createdcreated.substr(50);}if(created.length()0)coutcreated\n;}return0;}总结本题通过直接构造所有循环移位并排序实现了Burrows–Wheeler\texttt{Burrows–Wheeler}Burrows–Wheeler变换。核心步骤简洁明了适用于NNN较小的情况。实际应用中BWT\texttt{BWT}BWT通常配合其他压缩算法如游程编码、哈夫曼编码等使用。本题作为算法实现练习重点在于掌握循环移位的生成、字典序排序以及索引记录。注意输入跨行处理和输出格式控制。