नुथ-मॉरिस-प्रैट एल्गोरिदम

नुथ मॉरिस प्रैट (KMP) एक एल्गोरिदम है, जो कैरेक्टर को बाएं से दाएं चेक करता है। जब एक पैटर्न में एक सब-पैटर्न सब-पैटर्न में एक से अधिक बार प्रकट होता है, तो यह उस गुण का उपयोग समय जटिलता में सुधार के लिए करता है, सबसे खराब स्थिति के लिए भी।

KMP की समय जटिलता O(n) है।

इनपुट और आउटपुट

इनपुट: मुख्य स्ट्रिंग: "AAAABAAAAABBBAAAAB", पैटर्न "AAAB" आउटपुट: पैटर्न स्थान पर मिला: 1 पैटर्न स्थान पर मिला: 7 पैटर्न स्थान पर मिला: 14

एल्गोरिदम

findPrefix(pattern, m, prefArray)

इनपुट - पैटर्न, पैटर्न की लंबाई और प्रीफिक्स स्थान स्टोर करने के लिए एक ऐरे

आउटपुट - वह ऐरे जहां प्रीफिक्स स्थित हैं

Begin 
  length := 0 
  prefArray[0] := 0 
  for all character index 'i' of pattern, do 
    if pattern[i] = pattern[length], then 
      increase length by 1 
      prefArray[i] := length 
    else 
      if length ≠ 0 then 
        length := prefArray[length - 1] 
        decrease i by 1 
      else 
        prefArray[i] := 0 
  done 
End

kmpAlgorithm(text, pattern)

इनपुट: मुख्य टेक्स्ट, और पैटर्न, जिसे खोजा जाएगा

आउटपुट - वह स्थान जहां पैटर्न मिले

Begin 
  n := size of text 
  m := size of pattern 
  call findPrefix(pattern, m, prefArray) 
  while i < n, do 
    if text[i] = pattern[j], then 
      increase i and j by 1 
    if j = m, then 
      print the location (i-j) as there is the pattern 
      j := prefArray[j-1] 
    else if i < n AND pattern[j] ≠ text[i] then 
      if j ≠ 0 then 
        j := prefArray[j - 1] 
      else 
        increase i by 1 
  done 
End

उदाहरण

#include<iostream> using namespace std; void findPrefix(string pattern, int m, int prefArray[]) { int length = 0; prefArray[0] = 0; //first place is always 0 as no prefix for(int i = 1; i

आउटपुट
Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14