解題區/解題區 - UVa

UVa 715 - Substitution Cipher

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Solution

Problem

給一串加密過後的字典，其這一段字典按照原先的字典順序。假設只使用小寫字母的前 k 個單字，請問是否能正確解密，並且輸出明文是什麼。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac

Output

1
2
abcde
Message cannot be decrypted.

Solution

給定加密過後的字典，可以做相鄰的單詞比較，來得到字母間的大小關係，藉由拓撲排序得到與原先字母的對應關係。為了要正確解密，檢查拓撲過程中的瓶頸，相當於當前 queue 的大小為 1 來保證這個字母的對應關係。若不是瓶頸，則存在模稜兩可的解密。

由於密文不會使用所有的字母，只需要考慮密文使用的字母都能正確解密即可，意即前 k 個字母只有部分可逆轉換，密文仍然可以解。

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
#include <stdio.h> 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
char word[1024][1024], msg[1024];
char sbox[128];
int sfail[128];
int buildGraph(int n, int m)  {
    vector<int> g[128];
    int indeg[128] = {};
    for (int i = 1; i < n; i++) {
        int p = i-1, q = i;
        for (int j = 0; word[p][j] && word[q][j]; j++) {
            if (word[p][j] != word[q][j]) {
                g[word[p][j]].push_back(word[q][j]);
                indeg[word[q][j]]++;
                break;
            }
        }
    }
    
    deque<int> Q;
    for (int i = 'a'; i < 'a' + m; i++) {
        if (indeg[i] == 0) 
            Q.push_front(i);
    }
            
    int fail[128] = {}, order[128], ocnt = 0, u;
    while (!Q.empty()) {
        u = Q.front(), Q.pop_front();
        if (Q.size() >= 1) {
            for (deque<int>::iterator it = Q.begin();
                it != Q.end(); it++)
                fail[*it] = 1;
        }
        order[ocnt++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            if (--indeg[g[u][i]] == 0) {
                Q.push_back(g[u][i]);
            }
        }
    }
    for (int i = 'a'; i < 'a' + m; i++)
        if (indeg[i] > 0)
            sfail[i] = 1;
        
    for (int i = 0; i < 128; i++)
        sbox[i] = i;
    for (int i = 0; i < ocnt; i++)
        sbox[order[i]] = 'a' + i, sfail[order[i]] = fail[order[i]];
    return 1;
}
int decode(char msg[]) {
    for (int i = 0; msg[i]; i++) {
        if (sfail[msg[i]])
            return 0;
        msg[i] = sbox[msg[i]];
    }
    return 1;
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &m, &n);
        for (int i = 0; i < n; i++)
            scanf("%s", word[i]);
        while (getchar() != '\n');
        gets(msg);
        
        buildGraph(n, m);
        int f = decode(msg);
        if (!f) {
            puts("Message cannot be decrypted.");
        } else {
            puts(msg);
        }
    }
    return 0;
}
/*
tricky case:
1
5 5
a
eb
eec
eeed
eeee
e 
*/