P8085 [COCI 2011/2012 #4] KRIPTOGRAM
题目描述
现有一段明文和一部分密文。明文和密文都由英文单词组成，且密文中的一个单词必然对应着明文中的一个单词。
求给出的密文在明文中可能出现的最早位置。
输入格式
第一行，若干个英文单词和一个 $，表示明文。
第二行，若干个英文单词和一个 $，表示密文。
每行末尾的 $ 用于表示该行结束。数据保证没有多个 $ 出现在同一行的情况。
输出格式
输出密文在明文中可能出现的最早位置，即密文的第一个单词在明文中可能出现的最早位置。
输入输出样例 #1
输入 #1
a a a b c d a b c $ x y $输出 #1
3输入输出样例 #2
输入 #2
xyz abc abc xyz $ abc abc $输出 #2
2输入输出样例 #3
输入 #3
a b c x c z z a b c $ prvi dr prvi tr tr x $输出 #3
3说明/提示
【数据规模与约定】
- 对于100 % 100\%100%的数据，明文和密文所对应字符串的长度不超过10 6 10^6106，输入的单词均由小写字母组成。
【提示与说明】
题目译自 COCI 2011-2012 CONTEST #4Task 6 KRIPTOGRAM。
本题分值按 COCI 原题设置，满分140 140140。
C++实现
#include<bits/stdc++.h>#defineup(l,r,i)for(inti=l,END##i=r;i<=END##i;++i)#definedn(r,l,i)for(inti=r,END##i=l;i>=END##i;--i)usingnamespacestd;typedeflonglongi64;constintINF=2147483647;constintMAXN=1e6+3;intL1[MAXN],R1[MAXN];intL2[MAXN],R2[MAXN];intA[MAXN],B[MAXN],n,m;typedefunsignedintu32;typedefunsignedlonglongu64;constu64 BAS=13331;u64 H[MAXN],P[MAXN];map<string,int>M;intmain(){string t;while(cin>>t&&t!="$"){R1[M[t]]=++n,L1[n]=M[t],M[t]=n;}M.clear();while(cin>>t&&t!="$"){R2[M[t]]=++m,L2[m]=M[t],M[t]=m;}for(inti=1;i<=n;++i)if(!R1[i])R1[i]=INF;for(inti=1;i<=m;++i)if(!R2[i])R2[i]=INF;for(inti=1;i<=n;++i)A[i]=L1[i]?i-L1[i]:-1;for(inti=1;i<=m;++i)B[i]=L2[i]?i-L2[i]:-1;u64 h0=0,h=0;P[0]=1;for(inti=1;i<=m;++i)P[i]=P[i-1]*BAS;for(inti=1;i<=m;++i)h0=h0*BAS+B[i],h=h*BAS+A[i];if(h==h0)printf("%d\n",1),exit(0);for(inti=m+1;i<=n;++i){h=h*BAS+A[i],h=h-A[i-m]*P[m];if(R1[i-m]<=i){h=h-A[R1[i-m]]*P[i-R1[i-m]];A[R1[i-m]]=-1;h=h+A[R1[i-m]]*P[i-R1[i-m]];}elseif(R1[i-m]<=n)A[R1[i-m]]=-1;if(h==h0)printf("%d\n",i-m+1),exit(0);}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
