思路与算法

比较字典相邻两个单词，只在第一个不同字母处加入先后关系边。若前词比后词长但后词是前词前缀，则矛盾。对出现过的密文字母做Kahn拓扑排序，每一步必须恰有一个入度0的未取字母；没有则有环，多于一个则顺序不能唯一确定。唯一顺序的第i个密文字母还原为明文第i个字母。待恢复串出现词典外字母时输出0。

正确性说明

字典序由第一处不同字母决定；若一词是另一词的前缀，则短词必须在前。所以得到的约束恰是维持相邻字典序所必需且充分的条件，继而维持整张字典的顺序。偏序存在唯一线性扩张当且仅当Kahn每一步只有一个可取点：多个可取点可以交换形成至少两个顺序，无可取点则存在有向环。按修订明确的前m字母先验，唯一秩序就唯一确定解密映射。

复杂度

设字典总字符数L、待恢复串长度R，字符种数σ≤26。读入和比较O(L)，初始化与拓扑过程O(σ²)，翻译O(R)。流式仅保留相邻两词和待恢复串，空间O(σ²+最大词长+R)。

易错点

不能从同一单词内部字母顺序推导字母大小。重复词不加约束。长词在其短前缀之前是矛盾。必须明确本地缩减字母表先验，不能凭五个已见字母声称已恢复全部26种字母。未出现的待译字母和不唯一约束都输出0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    bool edge[26][26] = {}, exists[26] = {};
    int in[26] = {};
    string prev, word;
    bool ok = true;
    for (int i = 0; i < k; ++i) {
        cin >> word;
        for (char c : word)
            exists[c - 'a'] = true;
        if (i) {
            int j = 0;
            while (j < (int)min(prev.size(), word.size()) && prev[j] == word[j])
                ++j;
            if (j == (int)word.size() && prev.size() > word.size())
                ok = false;
            else if (j < (int)min(prev.size(), word.size())) {
                int a = prev[j] - 'a', b = word[j] - 'a';
                if (!edge[a][b]) {
                    edge[a][b] = true;
                    ++in[b];
                }
            }
        }
        prev = word;
    }
    string text;
    cin >> text;
    for (char c : text)
        if (!exists[c - 'a'])
            ok = false;
    string order;
    bool used[26] = {};
    int total = count(exists, exists + 26, true);
    for (int j = 0; j < total; ++j) {
        int v = -1;
        for (int i = 0; i < 26; ++i)
            if (exists[i] && !used[i] && !in[i]) {
                if (v != -1)
                    ok = false;
                v = i;
            }
        if (v < 0) {
            ok = false;
            break;
        }
        used[v] = true;
        order += char('a' + v);
        for (int i = 0; i < 26; ++i)
            if (edge[v][i])
                --in[i];
    }
    if (!ok) {
        cout << "0\n";
        return 0;
    }
    char map[26];
    for (int i = 0; i < total; ++i)
        map[order[i] - 'a'] = 'a' + i;
    for (char c : text)
        cout << map[c - 'a'];
    cout << "\n";
}