题目链接：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.
- If there are no shifts that would satisfy the condition of being a part of the unencrypted , print
- If there is exactly one shift that could have been used, print
#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.
显然是一道 KMP 题，由于 较小，故考虑直接枚举 加密后所有可能的密文，即枚举 ，然后对每个 的密文应用 KMP 算法，查找其在主串 中匹配的次数，只有次数为 1 时表示此 有效，然后统计所有有效的 即可。