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) के लिए लागू करने का प्रयास करें ।