UVA12604「Caesar Cipher」
UVA12604「Caesar Cipher」
1. 题目
题目链接：UVA12604「Caesar Cipher」 。
Description
In cryptography, a Caesar cipher, also known as Caesar’s cipher, the shift cipher, Caesar’s code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet (wrapping around in the end). For example, given an alphabet of capital letters in usual order, with a shift of 3, A would be replaced by D, B would become E, and so on, with Z being replaced by C. The method is named after Julius C Caesar, who used it in his private correspondence.
We are given an alphabet A, a string S which is encrypted using a shift cipher and a plaintext word W. Find the possible values of shifts (in the range [0, |A|-1] ）used in encryption if we know that the unencrypted text contains exactly one occurrence of the word W.
Input
Input starts with an integer N on a line, the number of test cases. Each cases contains three strings on separate lines, alphabet A, plaintext wordW and encrypted text S. Alphabet A will contain only letters and digits (['A'-'Z']['a'-'z']['0'-'9']) and its symbol order is not necessarily lexicographical (see the third sample case). A will not contain duplicate symbols. The constraints are as given: 3 \leq |A| \leq 62; 1 \leq |W| \leq 50,000; 3 \leq |S| \leq 500,000 .
Output
For each test case print one line of output.
- If there are no shifts that would satisfy the condition of W being a part of the unencrypted S, print
no solution. - If there is exactly one shift that could have been used, print
unique: #where#is the shift value. - It there are more than one possible shifts print
ambiguous:followed by the sorted list of shift values.
For clarification, see the sample output.
Sample Input
4
ABC
ABC
ABCBBBABC
ABC
ABC
ABCBCAABC
D7a
D7a
D7aaD77aDD7a
ABC
ABC
ABCSample Output
no solution
unique: 1
ambiguous: 1 2
unique: 02. 题解
分析
显然是一道 KMP 题，由于 |A| 较小，故考虑直接枚举 W 加密后所有可能的密文，即枚举shift = 0..|A|-1 ，然后对每个 W的密文应用 KMP 算法，查找其在主串 S 中匹配的次数，只有次数为 1 时表示此 shift 有效，然后统计所有有效的 shift 即可。
代码
#include <bits/stdc++.h>
using namespace std;
// KMP 算法
struct KMP {
#ifndef _KMP_
#define ll int
#define MAXN 500005
#endif
ll next[MAXN];
KMP() {}
// 计算失配数组 next
void getNext(char *str, ll n) {
next[0] = -1;
ll i = 0, j = -1;
while(i < n) {
if(!(~j) || str[i] == str[j]) {
++i, ++j;
if(str[i] != str[j]) next[i] = j;
else next[i] = next[j];
} else {
j = next[j];
}
}
}
// 计算主串中模式串的个数
ll match(char *main, ll n, char *pattern, ll m) {
ll ans = 0;
ll i = 0, j = 0;
while(i < n) {
if(!(~j) || main[i] == pattern[j]) {
++i, ++j;
if(j == m) {
++ans;
j = next[j];
}
} else {
j = next[j];
}
}
return ans;
}
};
int main()
{
ll t;
KMP kmp;
char set[MAXN], word[MAXN], text[MAXN], sword[MAXN];
ll pos[128];
scanf("%d", &t);
for(ll i = 0; i < t; ++i) {
scanf("%s%s%s", set, word, text);
ll s = strlen(set);
ll m = strlen(word);
ll n = strlen(text);
for(ll j = 0; j < s; ++j) {
pos[set[j]] = j;
}
vector <ll> ans;
for(ll j = 0; j < s; ++j) {
for(ll k = 0; k < m; ++k) {
sword[k] = set[(pos[word[k]]+j)%s];
}
kmp.getNext(sword, m);
if(kmp.match(text, n, sword, m) == 1) {
ans.push_back(j);
}
}
if(ans.empty()) {
printf("no solution\n");
} else if(ans.size() == 1) {
printf("unique: %d\n", ans[0]);
} else {
printf("ambiguous:");
for(ll i = 0; i < ans.size(); ++i) {
printf(" %d", ans[i]);
}
printf("\n");
}
}
return 0;
}腾讯云开发者
