Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem C: 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 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 Format

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<=|A|<=62, 1<=|W|<=50,000, 3<=|S|<=500,000.

Output Format

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

---

凱薩加密法，A 作為基礎的一般字母順序表。
位移時也必須查找 A 表。
而現在明文為 W，加密文件為 S。
找到可能的位移種類，使得 S 只會出現在 加密後的 W 一次。

窮舉做 KMP。

#include <stdio.h>
#include <string.h>
char A[1024], W[500005], S[500005];
int kmpTable[500005];
void KMPtable(char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPMatching(char T[], char P[], int tlen, int plen) {
    int i, j;
    int matchCnt = 0;
    for(i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            matchCnt++;
            j = kmpTable[j];
            if(matchCnt >= 2)
                return matchCnt;
        }
    }
    return matchCnt;
}
char E[500005];
int main() {
    int testcase;
    int i, j, k;
    scanf("%d", &testcase);
    while(getchar() != '\n');
    while(testcase--) {
        gets(A);
        gets(W);
        gets(S);
        int Alen = strlen(A);
        int Wlen = strlen(W);
        int Slen = strlen(S);
        int CHAR[1024] = {};
        for(i = 0; A[i]; i++)
            CHAR[A[i]] = i;
        int ret[1024], ridx = 0;
        for(i = 0; i < Alen; i++) {
            for(j = 0; j < Wlen; j++)
                E[j] = A[(CHAR[W[j]]+i)%Alen];
            E[Wlen] = '\0';
            KMPtable(E, Wlen);
            int cnt = KMPMatching(S, E, Slen, Wlen);
            if(cnt == 1)
                ret[ridx++] = i;
        }
        if(ridx == 0)
            puts("no solution");
        else if(ridx == 1)
            printf("unique: %d\n", ret[0]);
        else {
            printf("ambiguous:");
            for(i = 0; i < ridx; i++)
                printf(" %d", ret[i]);
            puts("");
        }
    }
    return 0;
}