本文主要是介绍HDU 4300 Clairewd’s message(拓展KMP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4300
题目大意：
发送一个密文，为字符串S。这段密文的前半部份是加密过的，后半部分是没有加密过的。现在这段密文被截获，但是密文的尾部的一部份损失了。例如，假设密文是xxxxzzzz, xxxx是加密过的，zzzz是没加密的，因为损失了后面一部份，所以截获的内容可能为xxxxzz， 可以保证截获的内容的无加密内容一定是完整的。
给出密码表，这个密码表为一串26个字母的字符串，a[0]表示a加密后的字母，a[1]表示b加密后的字母....a[25]表示z加密后的字母。
要你恢复到无损坏的密文。在截获的内容中，要让明文最短。
分析与总结：
先来看看暴力的方法是怎样的。直接从S的一半位置开始枚举，然后判断后面部分的经过加密后是否都和明文部分相匹配即可。
事实证明，数据弱了，可以暴力水过。
如果不水，这题的正解应该是用拓展KMP（资料）
先把S全部都当作是密文的，然后把S全转换成明文，保存为T
这时，S中的密文部分就全部都变成了明文，而明文部分都变成了xxx（不用管是什么）。
然后可以发现，原来的S中的明文部分是S的后缀，而T中的明文部分是T的前缀。
所以，演变成了求S【i....n】中的与T的最长公共前缀，就是赤裸的拓展KMP问题了。
代码：
1. 暴力
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int MAXN = 1000005;
char a[50];
char b[MAXN];
char str[MAXN];
int f[MAXN];
int val[200];int main(){int nCase;scanf("%d",&nCase);while(nCase--){scanf("%s %s",a,b);for(int i=0; a[i]; ++i){val[a[i]] = i+'a';}int len=strlen(b);int mid;if(len & 1) mid=len/2;else mid=len/2-1;int pos;for(int i=mid; i<len; ++i){bool flag=true;for(int k=0,j=i+1; j<len; ++j,++k){if(val[b[k]]!=b[j]){flag=false;break; }}if(flag){pos=i;break; }}memset(str, 0, sizeof(str));for(int i=0; i<=pos; ++i)str[i]=b[i];for(int i=pos+1,k=0; k<=pos; ++i,++k)str[i]=val[str[k]];puts(str);}return 0;
}2. 拓展KMP
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;typedef long long int64;
const int MAXN = 1000005;
char a[50];
char b[MAXN];
char str[MAXN];
int next[MAXN];
int extend[MAXN];
int hash[200];void getNext(const char *T){int len=strlen(T), a=0;next[0] = len;while(a<len-1 && T[a]==T[a+1]) ++a;next[1] = a;a=1;for(int k=2; k<len; ++k){int p=a+next[a]-1, L=next[k-a];if(k-1+L >= p){int j = (p-k+1)>0?(p-k+1):0;while(k+j<len && T[k+j]==T[j]) ++j;next[k] = j;a=k;}elsenext[k]=L;}
}
void EKMP(const char* S,const char* T){getNext(T);int slen=strlen(S), tlen=strlen(T), a=0;int minLen = min(slen,tlen);while(a<minLen && S[a]==T[a]) ++a;extend[0] = a;a=0;for(int k=1; k<slen; ++k){int p=a+extend[a]-1, L=next[k-a];if(k-1+L >= p){int j=max(p-k+1, 0);while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;extend[k] = j;a=k;}elseextend[k] = L;}
} int main(){int nCase;scanf("%d",&nCase);while(nCase--){scanf("%s %s",a,b);for(int i=0; a[i]; ++i){hash[a[i]] = i+'a';}memset(str, 0, sizeof(str));for(int i=0; b[i]; ++i){str[i] = hash[b[i]];}EKMP(b, str);int len=strlen(b);int maxi=len;for(int i=0; i<len; ++i){if(i+extend[i]>=len && i>=extend[i]){maxi=i;break;}}memset(str, 0, sizeof(str));for(int i=0; i<maxi; ++i){str[i]=b[i];str[maxi+i]=hash[b[i]];}puts(str);}return 0;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于HDU 4300 Clairewd’s message(拓展KMP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
