P1124 文件压缩网页链接P1124 文件压缩题目背景提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法它虽然只是单纯地对文件进行重排本身并不压缩文件但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。题目描述该算法具体如下对一个长度为n nn的字符串S SS首先根据它构造n nn个字符串其中第i ii个字符串由将S SS的前i − 1 i-1i−1个字符置于末尾得到。然后把这n nn个字符串按照首字符从小到大排序如果两个字符串的首字符相等则按照它们在S SS中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串S ′ SS′它的长度也是n nn并且包含了S SS中的每一个字符。最后输出S ′ SS′以及S SS的首字符在S ′ SS′中的位置p pp。举例S SS是example构造n nn个字符串。example xamplee ampleex mpleexa pleexam leexamp eexampl将字符串排序。ampleex example eexampl leexamp mpleexa pleexam xamplee压缩结果。S ′ xelpame S \texttt{xelpame}S′xelpamep 7 p 7p7由于英语单词构造的特殊性某些字母对出现的频率很高因此在S ′ SS′中相同的字母有很大几率排在一起从而提高S ′ SS′的压缩率。虽然这种算法利用了英语单词的特性然而在实践的过程中人们发现它几乎适用于所有的文件压缩。请你编一个程序读入S ′ SS′和p pp输出字符串S SS。保证S SS仅含小写字母所以输入的S ′ SS′也仅含小写字母。输入格式共三行。第一行是一个整数n nn1 ≤ n ≤ 10000 1 \le n \le 100001≤n≤10000代表S ′ SS′的长度。第二行是字符串S ′ SS′。第三行是整数p pp。输出格式一行S SS。输入输出样例 #1输入 #17 xelpame 7输出 #1example解题思路本题是Burrows-Wheeler 变换BWT的逆变换问题。给定变换后的字符串S ′ SS′和原字符串首字符在S ′ SS′中的位置p pp要求还原原始字符串S SS。该压缩算法本质上是对字符串的所有循环移位进行排序然后取尾字符组成S ′ SS′并记录原字符串在排序中的位置。逆变换过程需要利用排序后的首字符序列与尾字符序列之间的对应关系逐步还原原字符串。1. 问题等价转化设原始字符串为S SS长度为n nn。构造所有循环移位字符串S i S_iSi​0 ≤ i n 0 \le i n0≤in其中S i S_iSi​是将S SS的前i ii个字符移到末尾得到的。将这些循环移位字符串按规则排序先按首字符从小到大若首字符相同则按它们在S SS中的起始位置从小到大。排序后取每个字符串的最后一个字符按顺序组成字符串L S ′ L SLS′。同时原字符串S SS在排序后的位置为p pp1-based即S SS的首字符在L LL中的位置。排序后的首字符序列记为F FF。由于排序规则中首字符优先且稳定F FF恰好是L LL中所有字符按升序稳定排序的结果。逆变换的目标已知L LL和p pp还原S SS。2. 算法实现读取输入读入n nn、字符串S ′ SS′记为L LL和整数p pp。构建首字符序列F FF将L LL复制一份并排序得到F FF。初始化在F FF中找到第一个等于L [ p − 1 ] L[p-1]L[p−1]的字符记录其位置now并将该位置标记为已使用例如置为)。创建答案数组ans长度n nn。令ans[0] L[now]。迭代还原对于i 1 i 1i1到n − 1 n-1n−1在F FF中从后往前查找第一个等于L[now]的未使用字符记录其位置为新的now。将该位置标记为已使用。ans[i] L[now]。输出结果将ans数组逆序输出即得到原始字符串S SS。3. 复杂度分析时间复杂度排序L LL得到F FF需要O ( n log ⁡ n ) O(n \log n)O(nlogn)。迭代过程中每次需要在F FF中查找字符最坏情况每次扫描O ( n ) O(n)O(n)总时间复杂度O ( n 2 ) O(n^2)O(n2)。由于n ≤ 10000 n \le 10000n≤10000O ( n 2 ) O(n^2)O(n2)最坏约10 8 10^8108次操作在 1 秒时限内可接受。若需优化可预先建立字符到位置的索引将查找降至O ( 1 ) O(1)O(1)总复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度需要存储L LL、F FF和答案数组均为O ( n ) O(n)O(n)。总结本题通过模拟 BWT 逆变换过程还原原字符串。核心在于利用排序后首字符序列F FF与尾字符序列L LL的对应关系从主索引p pp开始交替在F FF中取第一个和最后一个匹配字符逐步构建出逆序的原字符串。算法思路直观代码实现简洁适合小规模数据。代码简要说明输入读入n nn字符串a S ′ a SaS′整数shou p。排序b a对b排序得到F FF。初始化在b中找到第一个等于a[shou-1]的字符位置now标记b[now] )。ans[0] a[now]。循环i从 1 到n − 1 n-1n−1在b中从后往前找等于a[now]的字符更新now标记ans[i] a[now]。输出逆序打印ans即为原字符串S SS。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,shou,now;cinn;string a,b,ans;cinashou;ba;sort(b.begin(),b.end());for(ll i0;in;i){if(b[i]a[shou-1]){nowi;b[i]);break;}}ans.resize(n);ans[0]a[now];for(ll i1;in;i){for(ll jn-1;j0;j--){if(b[j]a[now]){nowj;ans[i]a[now];b[j]);break;}}}for(ll in-1;i0;i--)coutans[i];return0;}