社区首页 >专栏 >UVA12604「Caesar Cipher」

UVA12604「Caesar Cipher」

hotarugali

发布于 2022-03-02 12:24:06

63700

代码可运行

文章被收录于专栏：hotarugaliの技术分享hotarugaliの技术分享

运行总次数：0

代码可运行

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 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

4
ABC
ABC
ABCBBBABC
ABC
ABC
ABCBCAABC
D7a
D7a
D7aaD77aDD7a
ABC
ABC
ABC

Sample Output

no solution
unique: 1
ambiguous: 1 2
unique: 0

2. 题解

分析

显然是一道 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;
}