Module: उपसर्ग फ़ंक्शन, Z फ़ंक्शन


Problem

10 /10


सिफ़र

Theory Click to read/hide

 
O(|S|) में एक स्ट्रिंग में एक सबस्ट्रिंग खोजने के लिए KMP(नथ-मॉरिस-प्रैट) एल्गोरिदम को लागू करने के लिए Z और फ़ंक्शन उपसर्ग दोनों का उपयोग किया जा सकता है। इस एल्गोरिथ्म का सार इस प्रकार है: हम उस स्ट्रिंग को विशेषता देते हैं जिसे हम उस स्ट्रिंग को खोजना चाहते हैं जिसमें हम खोज रहे हैं। इन पंक्तियों के बीच एक विभाजक वर्ण रखना अत्यधिक वांछनीय है, अर्थात एक ऐसा वर्ण जो किसी भी पंक्ति में नहीं होता है (आमतौर पर #)।

Problem

<दिव>

कॉरविन एरिक की टुकड़ी की गतिविधियों के बारे में n संदेशों को इंटरसेप्ट करने में सक्षम था। सच है, वे एन्क्रिप्टेड निकले, लेकिन इससे कोई फर्क नहीं पड़ता! क्या आप इन संदेशों को समझने में उसकी मदद करेंगे? यह मुश्किल नहीं होना चाहिए, क्योंकि कॉर्विन प्रत्येक मूल संदेश में कम से कम एक सबस्ट्रिंग जानता है।

एन्क्रिप्शन के लिए, एरिक एक सीजर सिफर का उपयोग करने के लिए जाना जाता है, यानी एक सिफर जिसमें नंबर i वाले अक्षर को नंबर <कोड वाले अक्षर से बदल दिया जाता है >i + k , जहाँ k कोई संख्या है।

चूंकि आधुनिक संकलक एम्बर वर्णमाला का समर्थन नहीं करते हैं, हम वर्णों को उनके सीरियल नंबर से बदल देंगे - 1 से 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 होना चाहिए


उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 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!