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, A1]$) 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 word $W$ 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
1 

Sample Output
1 

2. 题解
分析
显然是一道 KMP 题，由于 $A$ 较小，故考虑直接枚举 $W$ 加密后所有可能的密文，即枚举 $shift = 0..A1$，然后对每个 $W$ 的密文应用 KMP 算法，查找其在主串 $S$ 中匹配的次数，只有次数为 1 时表示此 $shift$ 有效，然后统计所有有效的 $shift$ 即可。
代码
1 

本博客所有文章除特别声明外，均采用 CC BYSA 4.0 协议 ，转载请注明出处！