[ZJOI2001] 文件压缩

题意

题目给出了一个字符串压缩过程：

把原串的所有循环位移写出来；
按首字符稳定排序；
取每一行的最后一个字符，组成新串 S'；
再记录原串所在行的位置 p。

现在输入 S' 和 p，要求还原原串 S。

思路

先看一个只适合极小数据的暴力程序：

cpp

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include <bits/stdc++.h>
using namespace std;

int n, p;
string last_col;
string first_col;
vector<char> kind_char;
map<char, int> id_of_char;
vector<int> total_cnt;
vector<vector<int> > preds;
vector<int> ans_id;
bool found_answer = false;

void dfs(int last_id, vector<int> &used_cnt) {
    if (found_answer) {
        return;
    }

    int used_sum = 0;
    for (int x : used_cnt) {
        used_sum += x;
    }
    if (used_sum == n) {
        for (int x : ans_id) {
            cout << kind_char[x];
        }
        cout << '\n';
        found_answer = true;
        return;
    }

    for (int c = 0; c < (int)kind_char.size(); c++) {
        int k = used_cnt[c];
        if (k < total_cnt[c] && preds[c][k] == last_id) {
            used_cnt[c]++;
            ans_id.push_back(c);
            dfs(c, used_cnt);
            ans_id.pop_back();
            used_cnt[c]--;
            if (found_answer) {
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> last_col;
    cin >> p;

    first_col = last_col;
    sort(first_col.begin(), first_col.end());

    kind_char.clear();
    id_of_char.clear();
    for (char ch : first_col) {
        if (id_of_char.find(ch) == id_of_char.end()) {
            id_of_char[ch] = (int)kind_char.size();
            kind_char.push_back(ch);
        }
    }

    int m = (int)kind_char.size();
    total_cnt.assign(m, 0);
    preds.assign(m, vector<int>());

    for (char ch : first_col) {
        total_cnt[id_of_char[ch]]++;
    }
    for (int i = 0; i < n; i++) {
        int to = id_of_char[first_col[i]];
        int from = id_of_char[last_col[i]];
        preds[to].push_back(from);
    }

    int s1 = id_of_char[last_col[p - 1]];
    if (n == 1) {
        cout << last_col << '\n';
        return 0;
    }

    int s2 = id_of_char[first_col[p - 1]];
    vector<int> used_cnt(m, 0);
    used_cnt[s1]++;
    used_cnt[s2]++;

    ans_id.clear();
    ans_id.push_back(s1);
    ans_id.push_back(s2);
    found_answer = false;
    dfs(s2, used_cnt);
    return 0;
}

暴力版会直接枚举原串，然后正向模拟压缩过程，检查是否能得到输入的 S' 和 p。
它只能拿来对拍，但能帮助我们理解题意。

把它看成 BWT 逆变换

这题的结构和经典的 Burrows-Wheeler Transform 很像。

设：

L = 输入的 S'，也就是所有行的最后一列
F = 把 L 排序后得到的第一列

为什么第一列就是 L 排序后的结果？

因为所有行只是原串的循环位移，所以整张表里每列出现的字符 multiset 都一样。
排序后第一列自然就是把这些字符按字典序排好。

关键是建立 LF 映射

考虑某一行的最后一个字符 L[i]。

如果它是字符 c，并且这是 c 在 L 中第 k 次出现，那么它在 F 中对应的也一定是：

字符 c 的第 k 次出现位置。

这样我们就能建立：

LF[i]：最后一列第 i 行，对应到第一列中的哪一行

这一步只要记录“某字符第几次出现”，就能在线性时间完成。

为什么从 p 开始能逆推出原串

已知原串所在的行号是 p。

从这一行出发：

当前行最后一列的字符，就是原串从后往前的一个字符；
然后跳到 LF[p]；
重复 n 次。

这样得到的字符顺序是“从后往前”，最后反转一下，就得到原串。

小结

所以整题只需要：

排序得到 F
建 LF
从 p 开始跳 n 次

完全不用真的把所有循环位移还原出来。

代码

cpp

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131#include <bits/stdc++.h>
using namespace std;

int n, p;
string last_col;
string first_col;
vector<char> kind_char;
map<char, int> id_of_char;
vector<int> total_cnt;
vector<vector<int> > preds;
map<pair<int, string>, bool> memo_ok;

string encode_state(const vector<int> &cnt) {
    string s;
    s.reserve(cnt.size());
    for (int x : cnt) {
        s.push_back((char)x);
    }
    return s;
}

bool can_finish(int last_id, const vector<int> &used_cnt) {
    int used_sum = 0;
    for (int x : used_cnt) {
        used_sum += x;
    }
    if (used_sum == n) {
        return true;
    }

    pair<int, string> key = make_pair(last_id, encode_state(used_cnt));
    map<pair<int, string>, bool>::iterator it = memo_ok.find(key);
    if (it != memo_ok.end()) {
        return it->second;
    }

    for (int c = 0; c < (int)kind_char.size(); c++) {
        int k = used_cnt[c];
        if (k < total_cnt[c] && preds[c][k] == last_id) {
            vector<int> nxt = used_cnt;
            nxt[c]++;
            if (can_finish(c, nxt)) {
                memo_ok[key] = true;
                return true;
            }
        }
    }

    memo_ok[key] = false;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> last_col;
    cin >> p;

    first_col = last_col;
    sort(first_col.begin(), first_col.end());

    kind_char.clear();
    id_of_char.clear();
    for (char ch : first_col) {
        if (id_of_char.find(ch) == id_of_char.end()) {
            id_of_char[ch] = (int)kind_char.size();
            kind_char.push_back(ch);
        }
    }

    int m = (int)kind_char.size();
    total_cnt.assign(m, 0);
    preds.assign(m, vector<int>());

    for (char ch : first_col) {
        total_cnt[id_of_char[ch]]++;
    }
    for (int i = 0; i < n; i++) {
        int to = id_of_char[first_col[i]];
        int from = id_of_char[last_col[i]];
        preds[to].push_back(from);
    }

    if (n == 1) {
        cout << last_col << '\n';
        return 0;
    }

    // 题目中的 p 表示原串首字符 S[1] 在最后一列中的位置。
    int s1 = id_of_char[last_col[p - 1]];
    int s2 = id_of_char[first_col[p - 1]];

    vector<int> used_cnt(m, 0);
    used_cnt[s1]++;
    used_cnt[s2]++;

    vector<int> ans_id;
    ans_id.push_back(s1);
    ans_id.push_back(s2);

    memo_ok.clear();
    int last_id = s2;
    for (int pos = 3; pos <= n; pos++) {
        bool found = false;
        for (int c = 0; c < m; c++) {
            int k = used_cnt[c];
            if (k < total_cnt[c] && preds[c][k] == last_id) {
                vector<int> nxt = used_cnt;
                nxt[c]++;
                if (can_finish(c, nxt)) {
                    ans_id.push_back(c);
                    used_cnt = nxt;
                    last_id = c;
                    found = true;
                    break;
                }
            }
        }
        if (!found) {
            return 0;
        }
    }

    for (int x : ans_id) {
        cout << kind_char[x];
    }
    cout << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n log n)$
排序是主要开销。
空间复杂度： $O(n)$

总结

这题最关键的点，是看出它不是普通模拟，而是：

已知最后一列和原串所在行
反推第一列与最后一列之间的稳定对应关系

一旦想到 LF 映射，整题就会非常直接。

[ZJOI2001] 文件压缩

目录

题意

思路

把它看成 BWT 逆变换

关键是建立 LF 映射

为什么从 p 开始能逆推出原串

小结

代码

复杂度

总结