题目链接:UVA12604「Caesar Cipher」 。
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 , would be replaced by , would become , and so on, with being replaced by . The method is named after Julius C Caesar, who used it in his private correspondence.
We are given an alphabet , a string which is encrypted using a shift cipher and a plaintext word Find the possible values of shifts (in the range )used in encryption if we know that the unencrypted text contains exactly one occurrence of the word.
Input starts with an integer on a line, the number of test cases. Each cases contains three strings on separate lines, alphabet plaintext word and encrypted text . Alphabet 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). will not contain duplicate symbols. The constraints are as given: .
For each test case print one line of output.
no solution
.unique: #
where #
is the shift value.ambiguous:
followed by the sorted list of shift values.For clarification, see the sample output.
4
ABC
ABC
ABCBBBABC
ABC
ABC
ABCBCAABC
D7a
D7a
D7aaD77aDD7a
ABC
ABC
ABC
no solution
unique: 1
ambiguous: 1 2
unique: 0
显然是一道 KMP 题,由于较小,故考虑直接枚举 加密后所有可能的密文,即枚举 ,然后对每个 的密文应用 KMP 算法,查找其在主串 中匹配的次数,只有次数为 1 时表示此 有效,然后统计所有有效的 即可。
#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;
}