Module: 前缀函数、Z函数


Problem

10 /10


密码

Theory Click to read/hide

 
Z 和函数前缀均可用于实现 KMP(Knuth-Morris-Pratt) 算法，用于在 O(|S|) 的字符串中查找子字符串。该算法的本质如下：我们将要查找的字符串归因于我们要查找的字符串。非常希望在这些行之间放置一个分隔符，即一个不出现在任何行中的字符（通常是#）。

Problem

<分区>

Corwin 能够截获 n 条关于 Eric 部队调动的消息。没错，它们竟然是加密的，但这没关系！你会帮助他破译这些信息吗？这应该不难，因为 Corwin 至少知道每条原始消息中的一个子字符串。

众所周知，Eric 使用凯撒密码进行加密，即用数字 替换数字 i 的字母的密码>i + k ，其中 k 是一些数字。

由于现代编译器不支持 Amber 字母，我们将用序列号替换字符 - 从 1 到 q 的数字，其中 < code> q - 字母表中的字符数。

每条消息的长度为 x，其解密的每个已知子字符串为 y。

您的目标是恢复所有原始消息。

带有 STD::STRING 的供应商将陷入混乱！！！
 
输入
第一行读取数字n (\(1 <= n <= 100\)) 和q < /code> (\(1 <= k <= 100\))
后面的3 * n行包含数字xi, yi (\(1 <= b_i <= a_i <= 100\)) 和 2 个数字数组，表示消息及其解密子字符串。

印记
在行号 i 中打印消息的解码版本，编号为 i。
此行末尾必须有 MUST NOT


例子
<头> <日># <正文>

time 250 ms
memory 16 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

输入 输出
1 1 11
10 4
11 7 1 1 2 6 7 1 1 8
2 7 7 8 		6 2 7 7 8 1 2 7 7 3