[UVA] 12604 - Caesar Cipher

題目連結

題意:

給3個字串，分別為
字元表 (會出現的字元)
明文字串
加密的字串

加密的字串解密後一定要出現恰1個明碼字串，
如果 == 1 就是 unique
如果 > 1 就是 ambiguous
如果 == 0 就是 no solution

加密就是指將明文字串的每個字元變成字元表上的下n個字元，
例如:
字元表
uvanice
明文
ane
加密的明文可能是
niu (shift 1)
icv (shift 2)
cea (shift 3)
依此類推
題目就是要求 n 為多少時，可以在加密字串中恰找到1個加密的明文

**************************************************

我的作法:

在母字串中找子字串
在這邊我記錄兩種方法，兩種方法都可以AC
一種是以hash方式，一種是KMP。

hash方式是將子字串丟進hash function得到1個hash值，
再去刷母字串，每次抓連續長度 m 的字串，其中 m = 子字串長度
一樣丟進hash function看是否有等於子字串的hash function。
至於hash function神奇地使用質數次方
f(str) = str[0] * p + str[1] * p^2 + str[2] * p^3 ...
p為質數(但不能為2，測試過會錯，這裡我使用7、37可以過，其他沒有測過)。
這方法神奇就在於字串hash值相同但字串不同的機率非常非常小，
也就是說通常hash值相同都是相同字串！！

KMP的部分可以參考維基百科，
簡單說就是先建立failure function，
在比對過程如果不對的話，子字串的指標要回到fail[前一個字元] + 1的位置，
若子字串的指標到了子字串尾巴，就count++，表示在母字串找到一個子字串了，
接著指標回到fail[前一個字元]+1。

兩種效率都很高，時間複雜度都是(n+m) ，hash效率稍微高一點。

**************************************************

程式碼:

/* 題目: UVa 12604 - Caesar Cipher
 * Language: C++
 * Created on: 2016年10月12日
 *   Author: hanting
 */
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
unsigned Base = 7; // 任一質數 // 不能2
int countStr(char *str, char *pat)
{
    int cnt = 0;
    unsigned  baseMax = 1;
    unsigned  strHash, patHash;
    strHash = str[0];
    patHash = pat[0];
    for(int i = 1; pat[i]; i++)
    {
        patHash = patHash*Base + pat[i];
        strHash = strHash*Base + str[i];
        baseMax *= Base;
    }
    if(patHash == strHash) cnt++;
    for(int i = strlen(pat), j = 0; str[i]; i++, j++)
    {
        strHash = (strHash - baseMax*str[j]) * Base + str[i];
        if(strHash == patHash) cnt++;
    }
    return cnt;
}
int fail[50005];
int KMP(char *str, char *pat)
{
    /*build failure function*/
    fail[0] = -1;
    int j;
    for(int i = 1; pat[i]; i++)
    {
        j = fail[i-1];
        while(j >= 0 && pat[i] != pat[j+1])
        {
            j = fail[j];
        }
        if(pat[i] == pat[j+1])
        {
            fail[i] = j+1;
        }
        else
        {
            fail[i] = -1;
        }
    }
    /*KMP*/
    int cnt = 0;
    j = 0;
    for(int i = 0; str[i]; i++)
    {
        while(j >= 1 && str[i] != pat[j])
        {
            j = fail[j-1] + 1;
        }
        if(str[i] == pat[j])
        {
            j++;
        }
        if(!pat[j])
        {
            cnt++;
            j = fail[j-1]+1;
        }
    }

    return cnt ;
}
char Alphabet[65], plainText[50005], encryptedText[500005];
int ans[50005];
int main()
{
    int testCase;
    scanf("%d", &testCase);
    while(testCase--)
    {
        int pos[128]; // pos['a'] = 0; pos['w'] = 1;// 表上'a'在第0個位置，下一個是'w'
        scanf("%s%s%s", Alphabet, plainText, encryptedText);
        for(int i = 0; Alphabet[i]; i++)
        {
            pos[Alphabet[i]] = i;
        }
        int AlphaL = strlen(Alphabet);
        Alphabet[AlphaL] = Alphabet[0];
        Alphabet[AlphaL+1] = 0;
        int ansi = 0;
        for(int i = 0; i < AlphaL; i++)
        {
            if(countStr(encryptedText, plainText) == 1)
            //if(KMP(encryptedText, plainText) == 1)
            {
                ans[ansi++] = i;
            }
            for(int j = 0; plainText[j]; j++)
            {
                int k = pos[plainText[j]]; // k在table中第幾個
                plainText[j] = Alphabet[k+1];
            }
        }
        if(ansi == 0)
        {
            puts("no solution");
        }
        else if(ansi == 1)
        {
            printf("unique: %d\n", ans[0]);
        }
        else
        {
            printf("ambiguous: ");
            for(int i = 0; i < ansi-1; i++)
            {
                printf("%d ", ans[i]);
            }
            printf("%d\n", ans[ansi-1]);
        }
    }
    return 0;
}