病毒(virus)

形式化题目

病毒对全文做同一个小写字母置换 $\pi$ ：每个字母被替换成另一个字母，位置、长度、顺序都不变。因此字典里 $K$ 个被感染的单词 $w_1, w_2, \dots, w_K$ 仍然满足

\pi^{-1}(w_1) < \pi^{-1}(w_2) < \dots < \pi^{-1}(w_K),

其中 $<$ 是通常的字符串字典序。给定这 $K$ 个密文单词和一个待还原的密文串 $t$ ，求 $\pi^{-1}$ 作用在 $t$ 上得到的明文串；若字典不足以唯一确定这个作用，输出 0。

样例

输入	输出
单词 `cebdbac` `cac` `ecd` `dca` `aba` `bac`，待还原 `cedab`	`abcde`

正解

思路

第一步：相邻词对能告诉我们什么。

字典序是由首个不同的字符决定的。设相邻两词 $u, v$ 首个不同的位置是 $j$ （下标从 1 开始），那么 $u < v$ 当且仅当 $\pi^{-1}(u_j) < \pi^{-1}(v_j)$ 。位置 $j$ 之后的字符完全不参与比较，提供不了任何信息。

于是每个相邻词对最多贡献一条约束：

\text{密的 } u_j \;\longrightarrow\; \text{密的 } v_j \qquad\text{表示「明的 } u_j \text{ 要排在 } v_j \text{ 前面」}

把所有这样的边收集起来，就得到一张 26 个结点以内的有向图 $G$ 。

以样例逐对拆开，5 个相邻词对给出 5 条边：

相邻词对	首个不同位置	该位置的密文字母	边
`cebdbac` , `cac`	第 2 位	`e` , `a`	`e` → `a`
`cac` , `ecd`	第 1 位	`c` , `e`	`c` → `e`
`ecd` , `dca`	第 1 位	`e` , `d`	`e` → `d`
`dca` , `aba`	第 1 位	`d` , `a`	`d` → `a`
`aba` , `bac`	第 1 位	`a` , `b`	`a` → `b`

把这 5 条边画出来，就是一条链——链就意味着一句话能数清谁排第几：

graph LR
    c((c)) --> e((e))
    e --> d((d))
    e --> a((a))
    d --> a
    a --> b((b))

从图中读出的唯一顺序是 c → e → d → a → b：c 是最小字母，b 是最大字母， e 在 d 与 a 之前，d 又在 a 之前。这个顺序就是明文序。

第二步：把明文序翻译成答案。

明文序中第 $i$ 个密文字母（从 0 数起）对应明文字母 chr(97 + i)。把样例的明文序 c, e, d, a, b 重编号：

位次	0	1	2	3	4
密文字母	`c`	`e`	`d`	`a`	`b`
明文字母	`a`	`b`	`c`	`d`	`e`

用这张表翻译 cedab，得到 abcde，与样例一致。

第三步：怎么判定"字典不完整或出错"。

这正是本题真正的难点，有三个出口，缺一不可：

约束成环 —— 字典自相矛盾。例如同时要求"明的 a 在 c 前"和"明的 c 在 a 前"，根本不存在这样的明文序。样例 3 就是这样：cabdbac, ccbdbac 给出边 a → c，而 ccbdbac, cac 又给出边 c → a，两条边打成一个环，输出 0。
同一层有多个候选 —— 字典给的信息不够多，存在不止一种合法明文序。用 Kahn 拓扑排序时，每一轮"入度为 0 的结点"就是当前可以排在最小的字母。只要某一轮同时有 $\geqslant 2$ 个这样的结点，把它们的先后对调仍然满足所有约束，说明字典无法唯一确定明文序。样例 1 逐轮的候选只有一个：

轮次候选候选个数弹出新入度为 0 累计顺序

1 c 1 c e c

2 e 1 e d c e

3 d 1 d a c e d

4 a 1 a b c e d a

5 b 1 b — c e d a b

候选个数始终是 1，所以明文序唯一。
待还原串用到了字典没覆盖的字母 —— 例如输入 1 / e / daead：字典只有一个字母 e，而 d、a 从未在字典里出现过。字典根本没有约束过它们的位置，自然无法还原。

轮次	候选	候选个数	弹出	新入度为 0	累计顺序
1	`c`	1	`c`	`e`	`c`
2	`e`	1	`e`	`d`	`c e`
3	`d`	1	`d`	`a`	`c e d`
4	`a`	1	`a`	`b`	`c e d a`
5	`b`	1	`b`	—	`c e d a b`

三个出口都用 0 表示，与"输出一个 0"的要求一致。

两个容易写错的地方。

第一，只有出现在"首个不同字母对"里的字母才可以进图。只在别处当普通字符出现的字母，一条边都不连着它，入度为 0，会被当成"最小字母"和真正的起点并列，把唯一的解误判成多解。举个会踩到的例子：字典 af, de, f —— 相邻词对给出 a → d、d → f，真正被定死的是 a, d, f 三者的相对顺序，字母 e 只是碰巧出现在 de 里；若把 e 也建点，第一轮就有 a 和 e 两个候选，会错误地输出 0。

第二，要跳过完全相同的相邻词对。排列是严格递增的，字典里本不该有重复词，但样例 2 就给了 dca, dca。若不跳过而直接去找"首个不同字符"， zip 会一路比到底、返回 None，看起来没事；但如果照着"位置从 1 数到 $\max$ 长度" 的写法去实现（参考实现就是这么写的），就会读到词尾之后的越界内容，凭空造出一条边。显式跳过是最稳的写法。

为什么每轮只要取"任意一个"入度 0 的结点就够了：拓扑排序的输出顺序不唯一，但本题要么有唯一解、要么就是 0；用最小堆取最小编号，只是为了让输出稳定、便于复现。

代码

Python 版：

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
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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 08:34
# update_at: 2026-09-30 08:34

import sys
from heapq import heapify, heappop, heappush

FAIL = '0'  # 字典残缺或自相矛盾时输出的唯一一个字符


def first_diff(u: bytes, v: bytes) -> tuple[int, int] | None:
    """相邻两词首个不同位置的字母对（密文前驱, 密文后继）；其中一个是另一个前缀时返回 None。"""
    for a, b in zip(u, v):
        if a != b:
            return a, b
    return None  # 例如 ac < acd：短词是长词前缀，不告诉任何字母的大小关系


def relation(words: list[bytes], i: int) -> tuple[int, int] | None:
    """第 i 与第 i+1 个词给出的字母大小关系；两词完全相同时这对词作废。"""
    if i + 1 < len(words) and words[i] == words[i + 1]:
        return None  # 排列严格递增，不该出现重复词，更不该让它的首不同对又去连一条边
    return first_diff(words[i], words[i + 1])


def recover(words: list[bytes], target: bytes) -> str:
    """还原明文串；字典不足以定序（成环或多解）时返回 FAIL。"""
    edges = set(filter(None, map(lambda i: relation(words, i), range(len(words) - 1))))
    # 只有当过"首不同对"主角的字母才被字典约束住；只作普通字符出现的字母进了图会冒充最小字母
    alphabet = sorted({c for a, b in edges for c in (a, b)})
    if not alphabet:                                 # 一个相邻词对都挑不出来：字典只剩一个字母的余地
        alphabet = sorted(set(target))               # 按明文序重编号后就是按字母表顺序，直接小写序
    succ = {c: set() for c in alphabet}              # 明文序中必须紧跟在 c 后面的那些字母
    for a, b in edges:
        succ[a].add(b)

    indeg = {c: 0 for c in alphabet}
    for d in succ.values():
        for x in d:
            indeg[x] += 1
    ready = [c for c in alphabet if not indeg[c]]
    heapify(ready)                                   # 每轮取最小编号，等价于反复扫候选表
    order: list[int] = []
    unique = True
    while ready:
        if len(ready) > 1:                           # 同时有两个可选字母 ⇒ 至少两种合法明文序
            unique = False
        c = heappop(ready)
        order.append(c)
        for d in succ[c]:
            indeg[d] -= 1
            if not indeg[d]:
                heappush(ready, d)

    if len(order) != len(alphabet) or not unique:    # 有环，或有字母的位置没被唯一确定
        return FAIL
    if not set(target) <= set(alphabet):             # 待还原串里出现了字典之外的字母
        return FAIL                                  # 说明这份字典根本没覆盖全部字母
    table = bytes.maketrans(bytes(order), bytes(range(97, 97 + len(order))))
    return target.translate(table).decode()          # 密文按明文序重编号，再换成 a,b,c,...


def solve() -> None:
    data = sys.stdin.buffer
    k = int(data.readline())
    words = [data.readline().strip() for _ in range(k)]
    target = data.readline().strip()
    print(recover(words, target))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:40
 * update_at: 2026-10-05 00:40
 */
#include <bits/stdc++.h>
using namespace std;

// 病毒把全文做同一个小写字母置换：密文里字母的“明文序”就是各密文字母按明文从小到大排的顺序。
// 相邻词对只由首个不同字母决定大小关系，于是每条这样的字母对就是图上一条有向边。

const int MAXK = 50005;
const int SIGMA = 26;

typedef long long ll;

ll k;
string words[MAXK]; // 感染后的字典，按密文字典序给出
string target;      // 待还原的密文串

bool edge_exist[SIGMA][SIGMA]; // edge_exist[u][v]：密文字母 u 的明文必须排在 v 的明文之前
bool is_node[SIGMA];           // 只有当过“首个不同字母对”主角的字母才配当图结点
int indeg[SIGMA];              // 每个结点的当前入度
int order[SIGMA];              // 拓扑序：order[i] 是明文序中第 i 小的密文字母
int order_cnt;

priority_queue<int, vector<int>, greater<int> > ready; // 入度为 0 的结点，取最小编号只为让结果稳定

void read_input() {
    cin >> k;
    for (ll i = 1; i <= k; i++) {
        cin >> words[i];
    }
    cin >> target;
}

// 相邻两词首个不同位置给出 u 的字母 → v 的字母这一条约束。
bool add_pair_edge(const string &u, const string &v) {
    ll ulen = u.size();
    ll vlen = v.size();
    ll len = min(ulen, vlen);
    for (ll j = 0; j < len; j++) {
        if (u[j] != v[j]) {
            int a = u[j] - 'a';
            int b = v[j] - 'a';
            edge_exist[a][b] = true;
            is_node[a] = true;
            is_node[b] = true;
            return true;
        }
    }
    return false; // 两词完全相同，或一个是另一个的前缀：不提供任何字母大小关系
}

void build_graph() {
    for (ll i = 1; i + 1 <= k; i++) {
        if (words[i] == words[i + 1]) {
            continue; // 排列严格递增，重复词作废，避免凭空造出一条边
        }
        add_pair_edge(words[i], words[i + 1]);
    }

    bool has_node = false;
    for (int c = 0; c < SIGMA; c++) {
        if (is_node[c]) {
            has_node = true;
        }
    }
    if (!has_node) {
        // 一个相邻词对都挑不出字母：此时只有目标串里的字母能确定，按字母表顺序重编号即可
        ll target_len = target.size();
        for (ll i = 0; i < target_len; i++) {
            is_node[target[i] - 'a'] = true;
        }
    }

    for (int u = 0; u < SIGMA; u++) {
        for (int v = 0; v < SIGMA; v++) {
            if (edge_exist[u][v]) {
                indeg[v]++;
            }
        }
    }
    for (int c = 0; c < SIGMA; c++) {
        if (is_node[c] && indeg[c] == 0) {
            ready.push(c);
        }
    }
}

void solve() {
    build_graph();

    int node_cnt = 0; // 结点最多 26 个，用 int
    for (int c = 0; c < SIGMA; c++) {
        if (is_node[c]) {
            node_cnt++;
        }
    }

    bool unique = true;
    while (!ready.empty()) {
        int candidate_cnt = ready.size();
        if (candidate_cnt > 1) {
            unique = false; // 同一轮出现多个候选：把它们的先后对调仍是合法明文序
        }
        int u = ready.top();
        ready.pop();
        order[order_cnt] = u;
        order_cnt++;
        for (int v = 0; v < SIGMA; v++) {
            if (edge_exist[u][v]) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    ready.push(v);
                }
            }
        }
    }

    if (order_cnt != node_cnt) {
        cout << 0 << "\n"; // 约束成环，字典自相矛盾
        return;
    }
    if (!unique) {
        cout << 0 << "\n"; // 字典给的信息不足，明文序不唯一
        return;
    }

    ll target_len = target.size();
    for (ll i = 0; i < target_len; i++) {
        if (!is_node[target[i] - 'a']) {
            cout << 0 << "\n"; // 目标串出现字典没约束过的字母
            return;
        }
    }

    // 明文序中第 i 小的密文字母，其明文就是 'a' + i，据此重编号翻译目标串
    char trans[SIGMA];
    for (int c = 0; c < SIGMA; c++) {
        trans[c] = 0;
    }
    for (int i = 0; i < order_cnt; i++) {
        trans[order[i]] = char('a' + i);
    }
    for (ll i = 0; i < target_len; i++) {
        cout << trans[target[i] - 'a'];
    }
    cout << "\n";
}

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

    read_input();
    solve();

    return 0;
}

复杂度

设字典的总字符数为 $S = \sum_i |w_i|$ ，字母表大小 $\sigma \leqslant 26$ ，边数 $E \leqslant \sigma^2$ 。

时间复杂度： $O(S)$ 建图（每个相邻词对扫描一次）+ $O(E \log \sigma)$ 拓扑排序 + $O(|t|)$ 翻译，总体 $O(S + \sigma^2 \log \sigma + |t|)$ 。 $K \leqslant 50000$ 时实测约 0.02 秒。
空间复杂度： $O(S)$ 存下所有单词，加上 $O(\sigma + E)$ 的图，实测峰值约 15 MB，远低于 128 MB。

总结

字典序只由首个不同字符决定，所以每个相邻词对最多提供一条不等式；把所有不等式建图，问题就变成"求拓扑序并判断是否唯一"。
判定"字典不完整"用的是 Kahn 拓扑排序的每轮候选个数，不是边的总数：只有在同一层同时出现两个可选字母时，才真的存在两种合法明文序。
判定"字典出错"（成环）用的是"弹出结点数是否等于字母表大小"。
两个高频实现陷阱：只有出现在首个不同字母对里的字母才配当图的结点；完全相同的相邻词对必须跳过，否则会读越界字符造出假边。
待还原串里出现字典外的字母时，字典没有覆盖全部字母，同样输出 0。

图示解析

下面把整条解题路线串起来：从相邻词对出发建图，在图上做拓扑排序，再用三个出口判定 0，最后用明文序重编号翻译目标串。

flowchart TD
    A["读入 K 个密文词 + 目标串"] --> B["对每个相邻词对<br/>找首个不同字母对"]
    B --> C{"两词完全相同<br/>或一个是另一个前缀?"}
    C -- 是 --> D["这一对不产生约束"]
    C -- 否 --> E["加边: 前驱字母 → 后继字母"]
    D --> F["只在边里出现过的字母<br/>组成结点集"]
    E --> F
    F --> G["Kahn 拓扑排序<br/>小根堆维护入度为 0 的结点"]
    G --> H{"弹出数 < 结点数?"}
    H -- 是 --> Z["输出 0<br/>（约束成环）"]
    H -- 否 --> I{"某轮候选个数 > 1?"}
    I -- 是 --> Z
    I -- 否 --> J{"目标串含<br/>字典外字母?"}
    J -- 是 --> Z
    J -- 否 --> K["第 i 个弹出的字母 ↔ 明文 chr(97+i)<br/>重编号翻译目标串"]
    K --> L["输出明文串"]

读图要点：菱形是三个独立的出错出口，任意一个成立都直接输出 0，不能只检查其中一个。左上的分叉决定了哪些字母有资格进图—— 这一步走错不会在样例上暴露，但会在"某字母只在无关位置出现"的数据上误判成多解。最下面的重编号框是本解与"直接输出明文序"写法的区别：答案长度必须与目标串一致。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析