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

Problem

कोडिंग सिद्धांत में, बिना उपसर्ग वाले कोड अक्सर शब्दों के सेट के रूप में उपयोग किए जाते हैं, इनमें से कोई भी उपसर्ग नहीं होता है। α शब्द β को उपसर्ग करने के लिए कहा जाता है यदि α को β से हटाकर प्राप्त किया जाता है अंत में शून्य या अधिक वर्ण। उदाहरण के लिए, a, ab और aba शब्द aba के उपसर्ग हैं। उदाहरण के लिए, शब्दों का समुच्चय aba, aa और bac एक अपरिफ़िक्स्ड कोड है, जबकि abac का समुच्चय , aba, ba मौजूद नहीं है क्योंकि aba शब्द abac का उपसर्ग है।

 प्रोफेसर डिसिफर बेकार सूचना अनुसंधान प्रयोगशाला में काम करते हैं और निकट-उपसर्ग कोड के अपने नए आविष्कार का अध्ययन करते हैं। शब्दों के एक सेट को k स्तर का लगभग उपसर्ग-मुक्त कोड कहा जाता है यदि सेट से किसी भी दो शब्दों का सबसे बड़ा सामान्य उपसर्ग लंबाई में k से अधिक नहीं होता है। उदाहरण के लिए, सेट abac, abc, ba लगभग अपरिफ़िक्स्ड लेवल 2 कोड है, और सेट abac , abab, ba मौजूद नहीं हैं क्योंकि abac और abab का सबसे लंबा सामान्य उपसर्ग 3 है।

 प्रोफेसर डेसिफ्रो ने अपने प्रयोगशाला सहायकों के लिए जो अगला कार्य निर्धारित किया है वह इस प्रकार है: शब्दों का एक सेट और एक संख्या k दिया गया है, इसे दिए गए में से चुनना आवश्यक है शब्द अधिकतम सेट, जो लगभग उपसर्ग-मुक्त स्तर कोड k है। आप, एक कनिष्ठ प्रयोगशाला सहायक के रूप में, संबंधित कार्यक्रम लिखने के लिए नियुक्त किए गए थे।