Module: Önek işlevi, Z işlevi


Problem

10 /10


şifre

Theory Click to read/hide

 
O(|S|) içindeki bir dizide bir alt dizi bulmak için KMP(Knuth-Morris-Pratt) algoritmasını uygulamak için hem Z hem de işlev öneki kullanılabilir. Bu algoritmanın özü şu şekildedir: Aradığımız diziyi bulmak istediğimiz diziye atfederiz. Bu satırların arasına bir ayırıcı karakter, yani herhangi bir satırda geçmeyen bir karakter (genellikle #) koymak çok arzu edilir.

Problem

Corwin, Eric'in birlik hareketleri hakkındaki n mesajlarını yakalamayı başardı. Doğru, şifreli oldukları ortaya çıktı, ama önemli değil! Bu mesajları deşifre etmesine yardım edecek misin? Corwin her orijinal mesajda en az bir alt dize bildiği için bu zor olmamalı.

Şifreleme için Eric'in bir Sezar şifresi, yani i numaralı harfin numaralı harfle değiştirildiği bir şifre kullandığı bilinmektedir. >i + k , burada k bir sayıdır.

Modern derleyiciler Amber alfabesini desteklemediğinden, karakterleri seri numaralarıyla değiştireceğiz - 1 ile q arasındaki bir sayı; burada < code> q - alfabedeki karakter sayısı.

Her mesaj x uzunluğundadır ve şifre çözme işleminin bilinen her alt dizisi y'dir.

Hedefiniz tüm orijinal mesajları geri yüklemektir.

STD::STRING OLUŞTURAN TEDARİKÇİ KAOSUN BAHÇELERİNE GİDECEK!!!
 
Giriş
İlk satırda n (\(1 <= n <= 100\)) ve q < sayıları okunur /code> (\(1 <= k <= 100\))
Aşağıdaki 3 * n satırları xi, yi sayılarını içerir > (\(1 <= b_i <= a_i <= 100\)) ve mesajı ve şifre çözme alt dizesini temsil eden 2 sayı dizisi.

Künye
i numaralı satıra, i numaralı mesajın çözülmüş halini yazdırın.
Bu satırın sonunda MUST NOT olmalıdır


Örnekler

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!

# Girdi Çıktı
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