Module: プレフィックス機能、Z機能


Problem

10 /10


暗号

Theory Click to read/hide

 
Z と関数プレフィックスの両方を使用して、O(|S|) の文字列内の部分文字列を見つけるための KMP(Knuth-Morris-Pratt) アルゴリズムを実装できます。このアルゴリズムの本質は次のとおりです。検索対象の文字列を、検索対象の文字列に帰属させます。これらの行の間に区切り文字、つまりどの行にも出現しない文字 (通常は #) を入れることが非常に望ましいです。

Problem

コーウィンは、エリックの軍隊の動きに関する n 件のメッセージを傍受できました。確かに、それらは暗号化されていることが判明しましたが、それは問題ではありません!彼がこれらのメッセージを解読するのを手伝ってくれますか? Corwin はすべての元のメッセージで少なくとも 1 つの部分文字列を知っているため、これは難しくありません。

暗号化のために、エリックはシーザー暗号を使用することが知られています。つまり、数字 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 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