केएमपी पर कई लेखों का उल्लेख है कि केएमपी में विफलता कार्य में बड़ी संख्या में अनुप्रयोग हैं।केएमपी विफलता समारोह के अनुप्रयोग
ऐसा एक एप्लिकेशन सबसे छोटी स्ट्रिंग को ढूंढ रहा है, जब कॉन्सटेनेटेड के समय मूल स्ट्रिंग (अवधि) देता है।
लेकिन मुझे कोई अन्य नहीं मिला। केएमपी विफलता समारोह में अन्य समस्याओं में क्या शामिल है?
केएमपी स्ट्रिंग के सभी उपसर्गों के सीमा की गणना करता है, जो स्वयं स्ट्रिंग पर एल्गोरिदम में एक महत्वपूर्ण धारणा है। (पूरे शब्द ही nontrivial है की सीमा गणना की जा रही है, और KMP (विफलता समारोह) है कि करने के लिए मानक है!)
रों की एक सीमा बस किसी भी शब्द है कि दोनों एक उपसर्ग और के प्रत्यय है।
आप ठीक ही देखा के रूप में, सीमाओं की गणना करने की क्षमता का एक उत्कृष्ट आवेदन संभावना सबसे छोटी स्ट्रिंग w इस तरह की गणना करने के लिए है कि कुछ प्राकृतिक कश्मीर के लिए डब्ल्यू^k = रों एक दिया स्ट्रिंग रों के लिए। इसे आदिम रूट कहा जाता है।
इसका कारण सीमाओं और स्ट्रिंग की अवधि के बीच द्वंद्व है। एक स्ट्रिंग रों का एक अवधि डब्ल्यूरों ऐसी है कि रों स्ट्रिंग wwww ... उदाहरण के लिए के उपसर्ग है, एबीसी से अधिक समय नहीं किसी भी स्ट्रिंग है अवधि है abcabcab। यह पता चला है कि सीमाओं और एक शब्द की अवधि के बीच 1: 1 पत्राचार है; ऊपर के उदाहरण में, ध्यान दें कि abcab abcabcab की एक सीमा है। सामान्य तौर पर, जब भी डब्ल्यूरों, तो स्ट्रिंग की अवधि उसकी शुरूआत से डब्ल्यूहटाने के बाद रों से बनी हुई है (डब्ल्यू^-1 रों) रों की एक सीमा है । इसी तरह, अगर डब्ल्यूरों, तो शब्द की एक सीमा है कि रों से बनी हुई है, जब आप w प्रत्यय हटाने रों की अवधि है।
तारों के गुणों का विश्लेषण करने में अवधि एक महत्वपूर्ण उपकरण है। तारों में पुनरावृत्ति (रन) खोजने के लिए उनका उपयोग एल्गोरिदम में उदाहरण के लिए किया जाता है; एक सिंहावलोकन के लिए this paper.
देखें