正題

---

題目大意

對于每個字母都有一個加密后的字母對應(yīng)。
然后給一段字母其中包括密文和密文對應(yīng)的原文的一部分(也有可能沒有原文)，求一段最短的密文加原文。

---

解題思路

枚舉密文和原文分界處。然后用字符串hash判斷改變后的密文和后段原文是否相等。

---

code

#include<cstdio> #include<cstring> #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-l+1];} ull lr2(int l,int r) {return h2[r]-h2[l-1]*pow[r-l+1];} int main() {scanf("%s",c);scanf("%s",s+1);n=strlen(s+1);pow[0]=1;for(int i=1;i<=n;i++){pow[i]=pow[i-1]*p;h1[i]=h1[i-1]*p+s[i]-'a';h2[i]=h2[i-1]*p+c[s[i]-'a']-'a';}//計算hashfor(int i=0;i<26;i++)r[c[i]-'a']=i+'a';//翻譯for(int i=n+2+(n&1)>>1;i<=n;i++){if(lr1(1,n-i+1)==lr2(i,n))//判斷是否為該密文的前一部分{for(int j=1;j<i;j++)//輸出原文printf("%c",s[j]);for(int j=1;j<i;j++)//輸出密文printf("%c",r[s[j]-'a']);return 0;}}for(int i=1;i<=n;i++)printf("%c",s[i]);for(int i=1;i<=n;i++)printf("%c",r[s[i]-'a']); }

總結(jié)

以上是生活随笔為你收集整理的nssl1192-加密【字符串hash】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。