题目的意思是给你一串长度为26的密钥,意味着abcd...xyz各自被加密成了什么字符。现在给出你另外一段由密文和明文组成的字符串,密文在前面,明文在后面,但是明文有可能不完整。如果明文不完整请补充完明文。


这个题看题目还是看的有点绕,看懂之后还是很容易的。假设把给出的文章串设为S1,那么我们可以把S1按照给出的密钥加密为S2,这样就把S1后面的明文加密了。然后判断加密后S2的后缀和未加密的S1前缀公共的最长长度(注意长度不能超过一半)。然后再把明文部分减去,把前面密钥部分再还原成明文放在后面输出即可。


(从来没在题目中用过hash,感觉都可以用map和kmp解决了,做这个题主要是熟悉下hash)


代码:

Problem : 4300 ( Clairewd’s message )     Judge Status : Accepted
RunId : 22090996    Language : G++    Author : chenshijinweb
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100005*2;
const int p=163;
int T;
char key[30], str[maxn], str2[maxn], pwd[30];
ULL px[maxn];
ULL hash1[maxn], hash2[maxn];
ULL get(int l, int r, ULL ht[]){
    return ht[r]-ht[l-1]*px[r-l+1];
}
void init(){
    int n=strlen(str+1);
    for(int i=1;i<=n;i++){
        str2[i]=key[str[i]-'a'];
    }
    str2[n+1]=0;
    px[0]=1;
    hash1[0]=hash2[0]=0;
    for(int i=1;i<=n;i++){
        px[i]=px[i-1]*p;
        hash1[i]=hash1[i-1]*p+str[i]-'a'+1;
        hash2[i]=hash2[i-1]*p+str2[i]-'a'+1;
    }
    for(int i=0;i<26;i++){
        pwd[key[i]-'a']=i+'a';
    }
}
void solve(){
    int len=strlen(str+1);
    int slen=len/2, i, j;
    for(i=slen;i>=1;i--){
        ULL h1=get(1, i, hash1);
        ULL h2=get(len-i+1, len, hash2);
        if(h1==h2)break;
    }
    for(j=1;j<=len-i;j++){
        str[j+len-i]=pwd[str[j]-'a'];
    }
    str[j+len-i]=0;
}
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%s%s", key, str+1);
        init();
        solve();
        printf("%s\n", str+1);
    }
    return 0;
}