নুথ-মরিস-প্র্যাট (KMP) অ্যালগরিদম

নুথ মরিস প্র্যাট (KMP) হলো একটি অ্যালগরিদম, যা ক্যারেক্টারগুলো বাম থেকে ডানে চেক করে। যখন একটি প্যাটার্নে সাব-প্যাটার্ন একাধিকবার দিয়ে থাকে, তবে সেটি সেই প্রোপার্টি ব্যবহার করে টাইম কমপ্লেক্সিটি উন্নত করে, ওৰ্স্ট কেসের জন্যও।

KMP-এর টাইম কমপ্লেক্সিটি O(n)।

ইনপুট এবং আউটপুট

ইনপুট: মেইন স্ট্রিং: "AAAABAAAAABBBAAAAB", প্যাটার্ন "AAAB" আউটপুট: Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14

অ্যালগরিদম

findPrefix(pattern, m, prefArray)

ইনপুট - প্যাটার্ন, প্যাটার্নের দৈর্ঘ্য এবং প্রিফিক্স লোকেশন স্টোর করার একটি অ্যারে

আউটপুট - প্রিফিক্স কোথায় আছে সেটি স্টোর করার অ্যারে

শুরু
  length := 0
  prefArray[0] := 0
  প্যাটার্নের সব ক্যারেক্টার ইনডেক্স 'i'-এর জন্য করুন
    যদি pattern[i] = pattern[length], তবে
      length 1 বাড়ান
      prefArray[i] := length
    অন্যথায়
      যদি length ≠ 0 হয়, তবে
        length := prefArray[length - 1]
        i 1 কমান
      অন্যথায়
        prefArray[i] := 0
  শেষ
শেষ

kmpAlgorithm(text, pattern)

ইনপুট: মেইন টেক্সট, এবং সার্চ করা প্যাটার্ন

আউটপুট - প্যাটার্ন যেখানে পাওয়া গেল সেসব লোকেশন

শুরু
  n := টেক্সটের সাইজ
  m := প্যাটার্নের সাইজ
  findPrefix(pattern, m, prefArray) কল করুন
  যতক্ষণ i < n, করুন
    যদি text[i] = pattern[j], তবে
      i এবং j 1 করে বাড়ান
    যদি j = m, তবে
      লোকেশন (i-j) প্রিন্ট করুন কারণ সেখানে প্যাটার্ন আছে
      j := prefArray[j-1]
    অন্যথায় যদি i < n AND pattern[j] ≠ text[i] হয়, তবে
      যদি j ≠ 0 হয়, তবে
        j := prefArray[j - 1]
      অন্যথায়
        i 1 বাড়ান
  শেষ
শেষ

উদাহরণ

#include<iostream> using namespace std; void findPrefix(string pattern, int m, int prefArray[]) { int length = 0; prefArray[0] = 0; //প্রথম প্লেস সবসময় 0 কারণ কোনো প্রিফিক্স নেই for(int i = 1; i<m; i++) { if(pattern[i] == pattern[length]) { length++; prefArray[i] = length; }else { if(length != 0) { length = prefArray[length - 1]; i--; //ইটারেশনের পর বাড়তেসি এফেক্ট এড়াতে i কমান }else prefArray[i] = 0; } } } void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) { int n, m, i = 0, j = 0; n = mainString.size(); m = pattern.size(); int prefixArray[m]; //প্যাটার্নের সাইজের সমান প্রিফিক্স অ্যারে findPrefix(pattern, m, prefixArray); loc = 0; while(i < n) { if(mainString[i] == pattern[j]) { i++; j++; } if(j == m) { locArray[loc] = i-j; //আইটেম i-j পজিশনে পাওয়া গেল। loc++; j = prefixArray[j-1]; //অ্যারে থেকে প্রিফিক্স দৈর্ঘ্য নিন }else if(i < n && pattern[j] != mainString[i]) { if(j != 0) j = prefixArray[j-1]; else i++; } } } int main() { string str = "AAAABAAAAABBBAAAAB"; string patt = "AAAB"; int locationArray[str.size()]; int index; kmpPattSearch(str, patt, locationArray, index); for(int i = 0; i<index; i++) { cout << "Pattern found at location: " <<locationArray[i] << endl; } }

আউটপুট

Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14