Clairewd’s message
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2398 Accepted Submission(s): 942
Problem Description
Clairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each letter of these messages would be transfered to another one according to a conversion table.
Unfortunately, GFW(someone's name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages.
But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won't overlap each other). But he doesn't know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you.
Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem.
Input
The first line contains only one integer T, which is the number of test cases.
Each test case contains two lines. The first line of each test case is the conversion table S. S[i] is the ith latin letter's cryptographic letter. The second line is the intercepted text which has n letters that you should recover. It is possible that the text is complete.
Hint
Range of test data:
T<= 100 ;
n<= 100000;
Output
For each test case, output one line contains the shorest possible complete text.
Sample Input
2
abcdefghijklmnopqrstuvwxyz
abcdab
qwertyuiopasdfghjklzxcvbnm
qwertabcde
Sample Output
abcdabcd
qwertabcde
題意比較難理解,就是說給定兩組字符串,第一組只有26個字符表對應明文中a,b,c,d....z可以轉換第一個,第二個...第26個字符變成密文,
第二組字符串是給定的密文+明文,明文可能不完整(缺失或沒有),叫你補完且整個密文+明文是最短的
如果有多種明文則取最大的明文
分析:因為可能有多種明文且密文>=明文,所以將字符串的前一半（一定是密文）轉換成明文和後一部分進行匹配,如果從後面某個位置能匹配到末尾,則表示那一部分是明文,然後進行補充完整輸出即可//這裡根據key得到密文轉換成明文的鑰匙b,不用明文轉換成密文匹配是因為明文可能有多種,後面一部分不一定是明文,根據b將密文轉換成明文(一定是最大的明文,因為b裡面轉換成的明文字符一定是最大的,比如key:aa....,則b:b.....)
EKMP:
[cpp]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 999999999
using namespace std;
const int MAX=100000+10;
char s1[MAX],s2[MAX],a[27],b[27];
int next[MAX];
void get_next(char *a,int len){
int k=0,i=1;
next[0]=len;//本題無作用
while(k+1<len && a[k] == a[k+1])++k;
next[1]=k;
k=1;
while(++i<len){
int maxr=k+next[k]-1;
next[i]=min(next[i-k],max(maxr-i+1,0));
while(i+next[i]<len && a[next[i]] == a[i+next[i]])++next[i];
if(i+next[i]>k+next[k])k=i;
}
}
int main(){
int T,k;
cin>>T;
while(T--){
cin>>a>>s1;
for(int i=0;i<26;++i)b[a[i]-'a']=i+'a';
int len=strlen(s1);
for(int i=0;i<(len+1)/2;++i)s2[i]=b[s1[i]-'a'];//將密文轉換為明文,密文長度>=明文長度
for(int i=(len+1)/2;i<=len;++i)s2[i]=s1[i];
get_next(s2,len);
for(k=(len+1)/2;k<len;++k){
if(next[k] == len-k)break;
}
cout<<s1;
for(int i=len-k;i<k;++i)cout<<b[s1[i]-'a'];
cout<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 999999999
using namespace std;
const int MAX=100000+10;
char s1[MAX],s2[MAX],a[27],b[27];
int next[MAX];
void get_next(char *a,int len){
int k=0,i=1;
next[0]=len;//本題無作用
while(k+1<len && a[k] == a[k+1])++k;
next[1]=k;
k=1;
while(++i<len){
int maxr=k+next[k]-1;
next[i]=min(next[i-k],max(maxr-i+1,0));
while(i+next[i]<len && a[next[i]] == a[i+next[i]])++next[i];
if(i+next[i]>k+next[k])k=i;
}
}
int main(){
int T,k;
cin>>T;
while(T--){
cin>>a>>s1;
for(int i=0;i<26;++i)b[a[i]-'a']=i+'a';
int len=strlen(s1);
for(int i=0;i<(len+1)/2;++i)s2[i]=b[s1[i]-'a'];//將密文轉換為明文,密文長度>=明文長度
for(int i=(len+1)/2;i<=len;++i)s2[i]=s1[i];
get_next(s2,len);
for(k=(len+1)/2;k<len;++k){
if(next[k] == len-k)break;
}
cout<<s1;
for(int i=len-k;i<k;++i)cout<<b[s1[i]-'a'];
cout<<endl;
}
return 0;
}
KMP:
[cpp]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 999999999
using namespace std;
const int MAX=100000+10;
char s1[MAX],s2[MAX],a[27],b[27];
int next[MAX];
void get_next(char *a,int len){
int i=-1,j=0;
next[0]=-1;
while(j<len){
if(i == -1 || a[i] == a[j])next[++j]=++i;
else i=next[i];
}
}
int main(){
int T;
cin>>T;
while(T--){
cin>>a>>s1;
for(int i=0;i<26;++i)b[a[i]-'a']=i+'a';
int len=strlen(s1),k=len;
for(int i=0;i<(len+1)/2;++i)s2[i]=b[s1[i]-'a'];//將密文轉換為明文,密文長度>=明文長度
for(int i=(len+1)/2;i<=len;++i)s2[i]=s1[i];
get_next(s2,len);
while(next[k]>len/2)k=next[k];
cout<<s1;
for(int i=next[k];i<len-next[k];++i)cout<<b[s1[i]-'a'];
cout<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 999999999
using namespace std;
const int MAX=100000+10;
char s1[MAX],s2[MAX],a[27],b[27];
int next[MAX];
void get_next(char *a,int len){
int i=-1,j=0;
next[0]=-1;
while(j<len){
if(i == -1 || a[i] == a[j])next[++j]=++i;
else i=next[i];
}
}
int main(){
int T;
cin>>T;
while(T--){
cin>>a>>s1;
for(int i=0;i<26;++i)b[a[i]-'a']=i+'a';
int len=strlen(s1),k=len;
for(int i=0;i<(len+1)/2;++i)s2[i]=b[s1[i]-'a'];//將密文轉換為明文,密文長度>=明文長度
for(int i=(len+1)/2;i<=len;++i)s2[i]=s1[i];
get_next(s2,len);
while(next[k]>len/2)k=next[k];
cout<<s1;
for(int i=next[k];i<len-next[k];++i)cout<<b[s1[i]-'a'];
cout<<endl;
}
return 0;
}
