洛谷P1124题解——文件压缩

First Post:

Last Update:

Word Count:
734

Read Time:
3 min

题目

原题链接：P1124-文件压缩

原题：

题目描述

该算法具体如下：对一个长度为 n 的字符串 S，首先根据它构造 n 个字符串，其中第 i 个字符串由将 S 的前 i−1 个字符置于末尾得到。然后把这 n 个字符串按照首字符从小到大排序，如果两个字符串的首字符相等，则按照它们在 S 中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 S′，它的长度也是 n，并且包含了 S 中的每一个字符。最后输出 S′ 以及 S 的首字符在 S′ 中的位置 p。

举例：S 是 example

  1. 构造 n 个字符串。

    1
    2
    3
    4
    5
    6
    7
    example
    xamplee
    ampleex
    mpleexa
    pleexam
    leexamp
    eexampl

  2. 将字符串排序。

    1
    2
    3
    4
    5
    6
    7
    ampleex
    example
    eexampl
    leexamp
    mpleexa
    pleexam
    xamplee

  3. 压缩结果。

    ，

在读题过程中不难发现，当我们将压缩结果按字典序排列时可以得到中首字母序列，从而我们可以得到每个字母的前驱或者后继。因此我们可以利用这个规律来找到原字符串。这里我们选择先找到尾字符，然后找每个字母的前驱，最后反向输出，这样做的原因是正向寻找时按照压缩字符串寻找，无规律，容易乱序，而逆向寻找靠排序串，不致乱序。

c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>//可食用头文件
using namespace std;
int main()
{
    int n,shou,now;//n为S串长度，shou即为题目中p，首字母所在压缩后的位置，now为现在进行到哪个位置了
    cin>>n;//输入
    char a[n],b[n],ans[n];//a——压缩串，b——字典序串，ans——答案串
    cin>>a>>shou;//万能cin
    for(int i=0;i<n;i++)b[i]=a[i];//a带给b
    sort(b,b+n);//自动排序
    for(int i=0;i<n;i++)//首先按首字母找到最后一个字母
    {
        if(b[i]==a[shou-1])
        {
            now=i;
            b[i]=')';//标记，退出
            break;
        }
    }
    ans[0]=a[now];//计入答案
    for(int i=1;i<n;i++)//ans[i]表示倒数第i+1个字母
    {
        for(int j=n-1;j>=0;j--)//从后往前搜到第一个与原char串匹配的字典序串
        {
            if(b[j]==a[now])
            {
                now=j;//更改现在所在位置，即跳到前一个字母
                ans[i]=a[now];//计入答案
                b[j]=')';//标记
                break;
            }
        }    
    }
    for(int i=n-1;i>=0;i--)cout<<ans[i];//倒序输出
}

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
n=int(input())#字符串长度
s=input()#压缩串
pos=int(input())#压缩串中首字母位置
pos=pos-1
box=[]#压缩串得到列表
for i in range(n):
    box.append(s[i])
boxs=box.copy()
boxs.sort()#字典序列表
res=[]
for i in range(0,n):
    if boxs[i]==box[pos]:
        pos=i
        boxs[i]='0'
        res.append(box[pos])
        break
    
for j in range(1,n):
    for i in range(n-1,-1,-1):
        if boxs[i]==box[pos]:
            pos=i
            res.append(box[pos])
            boxs[i]='0'
            break
            
ans=""
res.reverse()
for each in res:
    ans=ans+each
print(ans)




≡