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

O(n^3) asymptotics के साथ ट्रिवियल प्रीफ़िक्स फ़ंक्शन एल्गोरिद्म:

का उपयोग करके उत्पन्न किया गया
और अब हमें प्रपत्र की एक स्ट्रिंग के लिए एक उपसर्ग फ़ंक्शन बनाने की आवश्यकता है: & nbsp; t + # + s, जहां # एक सीमांकक वर्ण है जो पाठ में स्पष्ट रूप से नहीं है।  संबंधित विभाजक चरित्र के बाद उपसर्ग फ़ंक्शन के मूल्यों का विश्लेषण करते हुए, यह ध्यान दिया जाना चाहिए कि यदि परिणामी मान वांछित सबस्ट्रिंग की लंबाई के बराबर है, तो इसकी घटना पाई जाती है। उदाहरण के लिए, "abababcab" और वांछित सबस्ट्रिंग "अबाब", उपसर्ग समारोह होगा:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 हमें संबंधित स्ट्रिंग s:
के तत्वों को पार्स करने की आवश्यकता है 1 2 3 4 3 4 0 1 2 - ऐसे दो मामले हैं जहां मान 4 (चौथा और छठा) है, यानी लंबाई टी,  नतीजतन, उत्तर लिखा जाना चाहिए: 4 - 4 (लंबाई टी) & nbsp; = 0 और 6 - 4 = 2। यह देखा जा सकता है कि ये सही उत्तर हैं और स्ट्रिंग "अबाब" वास्तव में "abababcab" स्थिति 0 और 2 में।

 

इस समस्या को हल करने के लिए सामान्य गणना काम नहीं करेगी, क्योंकि इसके स्पर्शोन्मुख O(t*s) होंगे। इसलिए, सबस्ट्रिंग खोज कार्यों के लिए, KMP (नथ-मॉरिस-प्रैट) एल्गोरिथ्म का उपयोग किया जाता है। इस एल्गोरिथ्म को लागू करने के लिए, स्ट्रिंग उपसर्ग फ़ंक्शन का उपयोग किया जाता है, यह लंबाई n (strong>s लंबाई) की संख्याओं की एक सरणी है, जिसमें प्रत्येक तत्व  अधिकतम लंबाई है सबस्ट्रिंग s के सबसे बड़े स्वयं के प्रत्यय का, इसके उपसर्ग से मेल खाता हुआ। उदाहरण के लिए:   <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स"> <शरीर>
लाइन	उपसर्ग समारोह	ध्यान दें
अबाबाबकैब	0 0 1 2 3 4 0 1 2
एबीसीबीसीडी	0 0 0 1 2 3 0
आबाआब	0 1 0 1 2 2 3
उपसर्ग फ़ंक्शन को अनुकूलित करने के बाद (विवरण के लिए यहां), हमें O(n) स्पर्शोन्मुखता के साथ अंतिम एल्गोरिद्म मिलता है: का उपयोग करके उत्पन्न किया गया <पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स"> वेक्टर<int> उपसर्ग_फंक्शन (स्ट्रिंग एस) { int n = (int ) एस लंबाई (); वेक्टर<int> पाई (एन); के लिए (int i=1; i<n; ++i) { int j = pi[i-1< / स्पैन>]; जबकि (j > 0 && एस[i] != एस[जे]) j = pi[j-1]; अगर (s[i] == s[j]) ++ जे; pi[i] = j; } वापसीपी; } Training problem उपसर्ग समारोह
Z-फंक्शन Z-फंक्शन स्ट्रिंग S से - सरणी Z, जिसका प्रत्येक तत्व Z है [i ] स्ट्रिंग S में स्थिति i से शुरू होने वाले सबस्ट्रिंग के सबसे लंबे उपसर्ग के बराबर है, जो पूरे स्ट्रिंग का भी उपसर्ग है > जेड । स्थिति शून्य पर Z-फ़ंक्शन का मान आमतौर पर या तो शून्य होता है या पूरी स्ट्रिंग की लंबाई होती है। कठिनाई O(|S| ^ 2) या O(|S|)।   स्ट्रिंग S - सरणी P से उपसर्ग फ़ंक्शन, जिसका प्रत्येक तत्व P[i] सबसे लंबे प्रत्यय के बराबर है स्ट्रिंग S में स्थिति i से शुरू होने वाला सबस्ट्रिंग, जो पूरे स्ट्रिंग S का प्रत्यय भी है। स्थिति शून्य पर P-फ़ंक्शन का मान आमतौर पर या तो शून्य होता है या पूरी स्ट्रिंग की लंबाई होती है।  कठिनाई O(|S| ^ 2) या O(|S|)।   Z फ़ंक्शन और उपसर्ग फ़ंक्शन O(|S| ^ 2) के लिए लागू करने का प्रयास करें । Training problem जेड समारोह
O(|S|) में एक स्ट्रिंग में एक सबस्ट्रिंग खोजने के लिए KMP(नथ-मॉरिस-प्रैट) एल्गोरिदम को लागू करने के लिए Z और फ़ंक्शन उपसर्ग दोनों का उपयोग किया जा सकता है। इस एल्गोरिथ्म का सार इस प्रकार है: हम उस स्ट्रिंग को विशेषता देते हैं जिसे हम उस स्ट्रिंग को खोजना चाहते हैं जिसमें हम खोज रहे हैं। इन पंक्तियों के बीच एक विभाजक वर्ण रखना अत्यधिक वांछनीय है, अर्थात एक ऐसा वर्ण जो किसी भी पंक्ति में नहीं होता है (आमतौर पर #)। Training problem सिफ़र