7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】

【问题描述】

Alice和Bob正在悄悄地给对方发信息,信息都是由英文小写字母组成的,他们约定,所有的字母都得经过一个字母表进行变换,以防泄漏。另一方面John却在监听。

John发现,Alice和Bob通信的时候,总是先发送加密后的密文,然后紧接着发送原文。

但是Alice和Bob似乎也意识到了似乎有人监听,有时候会随意中断了他们的通信。不过每次都是在发送完密文之后才停止传送的。也就是说,John截获到的信息是密文的全文以及前一部分原文。原文可能一个字符都没有,也可能原文的全文都被截获。

现在John比较头疼,他虽然已经得到了他们两个人通信的加密字母表,但是分不清楚什么地方是密文和明文的分界线。你能帮他还原回完整的传输内容吗?

如果有多种可能时,John认为那个最短的信息才是原始的。

【输入格式】

第一行是密码表格,包含26个小写字母,依次表示a-z加密后的字母。

第二行是John截获到的通信信息。

【输出格式】

包含一行,表示还原后的通信信息。

【输入输出样例一】

recover.in recover.out
abcdefghijklmnopqrstuvwxyz

abcdab

abcdabcd

 

【输入输出样例二】

recover.in recover.out
qwertyuiopasdfghjklzxcvbnm

qwertabcde

qwertabcde

【数据规模】

    对于30%的数据:L<=100。

对于100%的数据:通信长度L<=100000。

继续阅读“7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】”