Module: تابع پیشوند، تابع Z


Problem

10 /10


رمز

Theory Click to read/hide

 
هم Z و هم پیشوند تابع را می توان برای پیاده سازی الگوریتم KMP(Knuth-Morris-Pratt) برای یافتن یک رشته فرعی در یک رشته در O(|S|) استفاده کرد. ماهیت این الگوریتم به شرح زیر است: ما به رشته ای که می خواهیم رشته ای را که در آن جستجو می کنیم نسبت می دهیم. بسیار مطلوب است که یک کاراکتر جداکننده بین این خطوط قرار دهید، یعنی کاراکتری که در هیچ خطی (معمولا #) وجود ندارد.

Problem

کوروین توانست پیام‌های n را در مورد تحرکات نیروهای اریک رهگیری کند. درست است، معلوم شد که آنها رمزگذاری شده اند، اما مهم نیست! آیا به او در رمزگشایی این پیام ها کمک می کنید؟ این نباید دشوار باشد، زیرا Corwin حداقل یک رشته فرعی را در هر پیام اصلی می داند.

برای رمزگذاری، اریک از رمز سزار استفاده می‌کند، یعنی رمزی که در آن حرف با عدد 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 وجود داشته باشد


مثال‌ها
<سر> <بدن>
# ورودی خروجی
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

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!