Module: 접두사 함수, Z 함수


Problem

10 /10


암호

Theory Click to read/hide

 
Z와 함수 접두사 모두 O(|S|)에서 문자열의 하위 문자열을 찾기 위한 KMP(Knuth-Morris-Pratt) 알고리즘을 구현하는 데 사용할 수 있습니다. 이 알고리즘의 본질은 다음과 같습니다. 검색하려는 문자열을 찾고자 하는 문자열에 귀속시킵니다. 이러한 줄 사이에 구분 문자, 즉 어떤 줄에도 나오지 않는 문자(보통 #)를 넣는 것이 매우 바람직합니다.

Problem

<사업부>

Corwin은 Eric의 병력 이동에 대한 n 메시지를 가로챌 수 있었습니다. 사실, 그들은 암호화된 것으로 판명되었지만 중요하지 않습니다! 그가 이 메시지를 해독하도록 도와주시겠습니까? Corwin은 모든 원본 메시지에서 하나 이상의 하위 문자열을 알고 있으므로 어렵지 않습니다.

암호화를 위해 Eric은 Caesar 암호, 즉 i라는 숫자가 있는 문자를 라는 숫자가 있는 문자로 대체하는 암호를 사용하는 것으로 알려져 있습니다. >i + k , 여기서 k는 숫자입니다.

최신 컴파일러는 Amber 알파벳을 지원하지 않기 때문에 문자를 해당 일련 번호(1에서 q까지의 숫자로 대체합니다. 여기서 < code> q - 알파벳의 문자 수.

각 메시지의 길이는 x이고 해독의 알려진 각 하위 문자열은 y입니다.

목표는 모든 원본 메시지를 복원하는 것입니다.

STD::STRING을 사용하는 공급업체는 혼란에 빠질 것입니다!!!
 
입력
첫 번째 줄은 숫자 n(\(1 <= n <= 100\)) 및 q <를 읽습니다. /코드> (\(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 111
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