解題區►解題區 - 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 
*/