佛山企业网站制作公司,沈阳网页设计培训,企业网站建设需要多少钱成都,以绿色为主的网站正题 题目大意
对于每个字母都有一个加密后的字母对应。 然后给一段字母其中包括密文和密文对应的原文的一部分(也有可能没有原文)#xff0c;求一段最短的密文加原文。 解题思路
枚举密文和原文分界处。然后用字符串hash判断改变后的密文和后段原文是否相等。 code
#inclu…正题 题目大意
对于每个字母都有一个加密后的字母对应。 然后给一段字母其中包括密文和密文对应的原文的一部分(也有可能没有原文)求一段最短的密文加原文。 解题思路
枚举密文和原文分界处。然后用字符串hash判断改变后的密文和后段原文是否相等。 code
#includecstdio
#includecstring
#define p 27
#define N 200010
#define ull unsigned long long
using namespace std;
char c[27],s[N]{0},r[27];
int n;
ull pow[N],h1[N],h2[N];
ull lr1(int l,int r)
{return h1[r]-h1[l-1]*pow[r-l1];}
ull lr2(int l,int r)
{return h2[r]-h2[l-1]*pow[r-l1];}
int main()
{scanf(%s,c);scanf(%s,s1);nstrlen(s1);pow[0]1;for(int i1;in;i){pow[i]pow[i-1]*p;h1[i]h1[i-1]*ps[i]-a;h2[i]h2[i-1]*pc[s[i]-a]-a;}//计算hashfor(int i0;i26;i)r[c[i]-a]ia;//翻译for(int in2(n1)1;in;i){if(lr1(1,n-i1)lr2(i,n))//判断是否为该密文的前一部分{for(int j1;ji;j)//输出原文printf(%c,s[j]);for(int j1;ji;j)//输出密文printf(%c,r[s[j]-a]);return 0;}}for(int i1;in;i)printf(%c,s[i]);for(int i1;in;i)printf(%c,r[s[i]-a]);
}
