Module: وظيفة البادئة ، وظيفة Z.


Problem

10 /10


الشفرة

Theory Click to read/hide

& nbsp؛
يمكن استخدام كل من Z وبادئة الوظيفة لتنفيذ خوارزمية KMP (Knuth-Morris-Pratt) للعثور على سلسلة فرعية في سلسلة في O (| S |). جوهر هذه الخوارزمية هو كما يلي: ننسب إلى السلسلة التي نريد إيجاد السلسلة التي نبحث فيها. من المستحسن للغاية وضع حرف فاصل بين هذه السطور ، أي حرف لا يظهر في أي سطر (عادة #).

Problem

تمكن كوروين من اعتراض رسائل n حول تحركات قوات إريك. صحيح ، لقد تبين أنها مشفرة ، لكن لا يهم! هل ستساعده في فك هذه الرسائل؟ لا ينبغي أن يكون هذا صعبًا ، حيث يعرف كوروين سلسلة فرعية واحدة على الأقل في كل رسالة أصلية.

للتشفير ، من المعروف أن إريك يستخدم تشفير قيصر ، أي تشفير يتم فيه استبدال الحرف الذي يحمل الرقم i بالحرف الذي يحمل الرقم i + k ، حيث يمثل k رقمًا ما.

نظرًا لأن المترجمات الحديثة لا تدعم الأبجدية الكهرمانية ، فسنستبدل الأحرف برقمها التسلسلي - رقم من 1 إلى q ، حيث < code> q - عدد الأحرف في الأبجدية.

طول كل رسالة x ، وكل سلسلة فرعية معروفة لفك تشفيرها هي y .

هدفك هو استعادة جميع الرسائل الأصلية.

سينتقل المورد الذي لديه STD :: STRING إلى ساحات الفوضى !!!
نبسب ؛
إدخال
يقرأ السطر الأول الأرقام n ( \ (1 & lt؛ = n & lt؛ = 100 \) ) و q < / code> ( \ (1 & lt؛ = k & lt؛ = 100 \) )
تحتوي سطور 3 * n التالية على أرقام x i ، y i ( \ (1 & lt؛ = b_i & lt؛ = a_i & lt؛ = 100 \) ) وصفيفتان من الأرقام تمثلان الرسالة وسلسلة فك تشفيرها الفرعية.

بصمة
في السطر رقم i اطبع نسخة الرسالة التي تم فك ترميزها بالرقم i .
يجب أن يكون هناك يجب ألا في نهاية هذا السطر


أمثلة <الجسم>
# إدخال الإخراج
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!