题目描述

本题要求实现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​，其中S0=SS_0 = SS0​=S，SkS_kSk​由Sk−1S_{k-1}Sk−1​将第一个字符移动到末尾得到。然后将这NNN个字符串按字典序排序，输出排序后矩阵的最后一列所组成的字符串，以及S1S_1S1​（即原串左移一位）在排序后的行号（从000开始）。

输入中字符串可能跨多行，每行（除最后一行外）恰好505050个字符。输出时，最后一列字符串也按每行505050个字符（最后一行可少于505050）输出。

输入格式

第一行为一个整数MMM，表示数据集的个数。随后可能有一个空行。每个数据集的第一行为整数NNN（N<1997N < 1997N<1997），表示字符串长度。接下来若干行包含该字符串，每行（除最后一行外）恰好505050个字符。数据集之间可能有一个空行。

输出格式

对于每个数据集，输出两行（或更多）：

• 第一行输出S1S_1S1​在排序后数组中的行号（从000开始计数）。
• 随后若干行输出变换后的最后一列字符串，每行最多505050个字符。

每组输出之间用一个空行分隔。

样例

输入

1 6 pascal

输出

1 cpsala

题目分析

Burrows–Wheeler\texttt{Burrows–Wheeler}Burrows–Wheeler变换是数据压缩中的经典预处理步骤，它通过重排字符使得具有相同上下文的字符聚集，便于后续压缩。本题要求实现最基本的变换过程：

1. 构造所有循环移位（共NNN个）。
2. 按字典序排序这些移位。
3. 提取排序后每个字符串的最后一个字符，拼接成新字符串。
4. 输出原串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)，当N=1997N = 1997N=1997时约为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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structcell{intlabel;string s;booloperator<(constcell&another)const{returns<another.s;}};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intdatasets;cin>>datasets;string line;for(intd=1;d<=datasets;d++){if(d>1)cout<<'\n';intlength;cin>>length;cin.ignore(1024,'\n');string word;while(true){getline(cin,line);word+=line;if(word.length()>=length)break;}string s0=word,s1=word;s1.push_back(s1.front());s1.erase(s1.begin());vector<cell>words;for(inti=0;i<length;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(inti=0;i<length;i++){created+=words[i].s.back();if(indexer==-1&&words[i].label==1)indexer=i;}cout<<indexer<<'\n';while(created.length()>50){cout<<created.substr(0,50)<<'\n';created=created.substr(50);}if(created.length()>0)cout<<created<<'\n';}return0;}

总结

本题通过直接构造所有循环移位并排序，实现了Burrows–Wheeler\texttt{Burrows–Wheeler}Burrows–Wheeler变换。核心步骤简洁明了，适用于NNN较小的情况。实际应用中，BWT\texttt{BWT}BWT通常配合其他压缩算法（如游程编码、哈夫曼编码等）使用。本题作为算法实现练习，重点在于掌握循环移位的生成、字典序排序以及索引记录。注意输入跨行处理和输出格式控制。