hdu4300 Clairewd’s message
2024-10-15 02:31:48
地址:http://acm.hdu.edu.cn/showproblem.php?pid=4300
题目:
Clairewd’s message
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6347 Accepted Submission(s): 2381
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.
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.
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
abcdefghijklmnopqrstuvwxyz
abcdab
qwertyuiopasdfghjklzxcvbnm
qwertabcde
Sample Output
abcdabcd
qwertabcde
qwertabcde
Author
BUPT
Source
思路:扩展kmp+枚举
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio> using namespace std;
const int K=1e6+;
int nt[K],extand[K];
char S[K],T[K],sa[K],tr[];
void Getnext(char *T,int *next)
{
int len=strlen(T),a=;
next[]=len;
while(a<len- && T[a]==T[a+]) a++;
next[]=a;
a=;
for(int k=; k<len; k++)
{
int p=a+next[a]-,L=next[k-a];
if( (k-)+L >= p)
{
int j = (p-k+)> ? (p-k+) : ;
while(k+j<len && T[k+j]==T[j]) j++;
next[k]=j;
a=k;
}
else
next[k]=L;
}
}
void GetExtand(char *S,char *T,int *next)
{
Getnext(T,next);
int slen=strlen(S),tlen=strlen(T),a=;
int MinLen = slen < tlen ? slen : tlen;
while(a<MinLen && S[a]==T[a]) a++;
extand[]=a;
a=;
for(int k=; k<slen; k++)
{
int p=a+extand[a]-, L=next[k-a];
if( (k-)+L >= p)
{
int j= (p-k+) > ? (p-k+) : ;
while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
extand[k]=j;
a=k;
}
else
extand[k]=L;
}
}
int main(void)
{
int t;cin>>t;
while(t--)
{
scanf("%s%s",S,T);
int len=strlen(T),st=;
for(int i=;i<;i++)
tr[S[i]]='a'+i;
for(int i=;i<len;i++)
sa[i]=tr[T[i]];
sa[len]=T[len];
GetExtand(T,sa,nt);
for(int i=(len+)/;i<len&&!st;i++)
if(extand[i]==len-i)
st=i-;
if(st==)st=len-;
for(int i=;i<=st;i++)
printf("%c",T[i]);
for(int i=;i<=st;i++)
printf("%c",tr[T[i]]);
printf("\n"); }
return ;
}
最新文章
- C#设计模式系列:职责链模式(Chain of Responsibility)
- VS开发中的代码编写小技巧&mdash;&mdash;避免重复代码编写的几种方法
- 一个App需要的东西
- MongoDB 入门之基础 DDL
- Run UliPad 4.1 Under Windows 7 64bit and wxPython 3.0.2
- jquery的is用法
- asp.net mvc3.0第一个程序helloworld开发图解
- Velocity+Java较全教程
- 利用VC/VS的安装目录找到C/C++库函数实现的源代码
- centos7和windows7双系统安装
- C primer plus 读书笔记第九章
- 安全:加固你的ssh 登录
- 在PHP中处理表单之—Checkbox
- 手机游戏产品经理(一)logo的印象非常重要,以促进
- 十四、Hadoop学习笔记————Zookeeper概述与基本概念
- 联想的笔记本有隐藏分区 导致无法安装win10 eufi启动 报错:windows无法更新计算机的启动配置。无法安装
- 【SVN】svn 查看项目的 svn 服务器地址目录(脱机状态下)
- UVA11584-Partitioning by Palindromes(动态规划基础)
- 什么是rpc
- 查看Andorid应用是32位还是64位