HDU-4300 Clairewd’s message

xiaoxiao2021-02-28  8

题目链接:https://vjudge.net/problem/HDU-4300

这道题理解了题意就容易想思路了,我看了别人的题解才理解了题意:

题目大意:

发送一个密文,为字符串S。这段密文的前半部份是加密过的,后半部分是没有加密过的。现在这段密文被截获,但是密文的尾部的一部份损失了。例如,假设密文是xxxxzzzz, xxxx是加密过的,zzzz是没加密的,因为损失了后面一部份,所以截获的内容可能为xxxxzz, 可以保证截获的内容的无加密内容一定是完整的。

给出密码表,这个密码表为一串26个字母的字符串,a[0]表示a加密后的字母,a[1]表示b加密后的字母....a[25]表示z加密后的字母。

要你恢复到无损坏的密文。在截获的内容中,要让明文最短。

所以可以使用扩展KMP算法

先将字符串S当做密文转换生成明文T

然后S是文本串,T是模式串,求T与S后缀的匹配,从S中间开始,找到最短的匹配

具体看代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; const int M=1e5+10; char a[N],b[M],c[26],c0[26]; int next0[M],extend[N]; void get_next() { int len=strlen(b); next0[0]=len; int i=0; while(i<len-1&&b[i]==b[i+1]) ++i; next0[1]=i; i=1; for(int k=2;k<len;++k) { int p=i+next0[i]-1; int L=next0[k-i]; if(k-1+L>=p) { int j=(p-k+1)>0?(p-k+1):0; while(k+j<len&&b[k+j]==b[j]) ++j; next0[k]=j; i=k; } else next0[k]=L; } } void get_extend() { int i=0,j,po,alen=strlen(a),blen=strlen(b); get_next(); while(a[i]==b[i]&&i<alen&&i<blen) i++; extend[0]=i; po=0; for(i=1;i<alen;i++) { if(next0[i-po]+i<extend[po]+po) extend[i]=next0[i-po]; else { j=extend[po]+po-i; if(j<0) j=0; while(i+j<alen&&j<blen&&a[j+i]==b[j]) j++; extend[i]=j; po=i; } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",c); for(int i=0;i<26;i++) c0[c[i]-'a']='a'+i; scanf("%s",a); int alen=strlen(a); for(int i=0;i<alen;i++) b[i]=c0[a[i]-'a']; b[alen]='\0'; get_extend(); int s=alen/2; if(alen%2) s++; //这里要注意,输出文本长度必须大于等于输入文本 for(int i=s;i<=alen;i++) //原来是i<alen,没考虑无匹配情况,WA了 if(extend[i]==alen-i) { for(int j=0;j<i;j++) printf("%c",a[j]); for(int j=0;j<i;j++) printf("%c",c0[a[j]-'a']); printf("\n"); break; } } return 0; }

转载请注明原文地址: https://www.6miu.com/read-2000109.html

最新回复(0)