題目鏈接：點(diǎn)擊查看

題目大意：給出兩個(gè)字符串 s 和 t ，字符串 s 代表著一種密碼的映射，字符串 t 代表著一段密文+明文，題目保證密文是完整的，但明文只有一部分，現(xiàn)在問(wèn)如何補(bǔ)全字符串 t ，使得字符串 t 的前半部分是密文，后半部分是明文，且明文和密文所表達(dá)的字符串經(jīng)過(guò)密碼映射后是一致的，且滿足補(bǔ)齊后的字符串 t 的長(zhǎng)度最短

題目分析：因?yàn)橐ＷC前后一致且最短，那么就挑選的位置盡可能靠前且滿足字符串 t 的后綴與前綴相等，說(shuō)道后綴與前綴相等，那就可以直接用擴(kuò)展KMP來(lái)解決了，求出extend數(shù)組后，找到一個(gè)位置 i ，滿足 i +extend[ i ] >=len ，且 i >=extend[ i ]，第一個(gè)滿足這兩個(gè)條件的位置就是切割位置了，找到這個(gè)位置之后就可以直接輸出了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100; //字符串長(zhǎng)度最大值int Next[N],extend[N];char s[N],t[N];unordered_map<char,char>decode;//預(yù)處理計(jì)算Next數(shù)組 void getNext(char str[]) {int i=0,j,po,len=strlen(str);Next[0]=len; //初始化Next[0]while(str[i]==str[i+1] && i+1<len) i++; Next[1]=i; //計(jì)算Next[1]po=1; //初始化po的位置for(i=2;i<len;i++){if(Next[i-po]+i < Next[po]+po) //第一種情況，可以直接得到Next[i]的值Next[i]=Next[i-po];else //第二種情況，要繼續(xù)匹配才能得到Next[i]的值{j = Next[po]+po-i;if(j<0) j=0; //如果i>po+Next[po],則要從頭開(kāi)始匹配while(i+j<len && str[j]==str[j+i]) j++; Next[i]=j;po=i; //更新po的位置}} }//計(jì)算extend數(shù)組 void EXKMP(char s1[],char s2[]) {int i=0,j,po,len=strlen(s1),l2=strlen(s2);getNext(s2); //計(jì)算子串的Next數(shù)組while(s1[i]==s2[i] && i<l2 && i<len) i++; extend[0]=i;po=0; //初始化po的位置for(i=1;i<len;i++){if(Next[i-po]+i < extend[po]+po) //第一種情況，直接可以得到extend[i]的值extend[i]=Next[i-po];else //第二種情況，要繼續(xù)匹配才能得到extend[i]的值{j = extend[po]+po-i;if(j<0) j=0; //如果i>extend[po]+po則要從頭開(kāi)始匹配while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; extend[i]=j;po=i; //更新po的位置}} }void init() {decode.clear();char str[30];scanf("%s",str);for(int i=0;i<26;i++)decode[str[i]]='a'+i; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();scanf("%s",s);//原碼 = 密文 + 明文int n=strlen(s); for(int i=0;i<n;i++)t[i]=decode[s[i]];//全部解密后的明文 getNext(s);EXKMP(s,t);int ans=n;for(int i=0;i<n;i++)if(i+extend[i]>=n&&i>=extend[i])//i為密文長(zhǎng)度，extend[i]為明文長(zhǎng)度{ans=i; break;}for(int i=0;i<ans;i++)putchar(s[i]);for(int i=0;i<ans;i++)putchar(decode[s[i]]);putchar('\n');}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4300 Clairewd’s message(扩展KMP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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