নেইভ প্যাটার্ন সার্চিং

নেইভ প্যাটার্ন সার্চিং অন্যান্য প্যাটার্ন সার্চিং অ্যালগরিদমের মধ্যে সবচেয়ে সহজ পদ্ধতি। এটি মেইন স্ট্রিংয়ের সব ক্যারেক্টার প্যাটার্নের সাথে চেক করে। এই অ্যালগরিদম ছোট টেক্সটের জন্য সহায়ক। এতে কোনো প্রি-প্রসেসিং ফেজ দরকার নেই। স্ট্রিংয়ের জন্য একবার চেক করে সাবস্ট্রিং খুঁজে পাওয়া যায়। অপারেশন করার জন্য এক্সট্রা স্পেসও এক্সপেন্ড করে না।

নেইভ প্যাটার্ন সার্চ মেথডের টাইম কমপ্লেক্সিটি O(m*n)। এখানে m হলো প্যাটার্নের সাইজ এবং n হলো মেইন স্ট্রিংয়ের সাইজ।

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

ইনপুট: মেইন স্ট্রিং: "ABAAABCDBBABCDDEBCABC", প্যাটার্ন: "ABC" আউটপুট: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18

অ্যালগরিদম

naivePatternSearch(pattern, text)

ইনপুট - টেক্সট এবং প্যাটার্ন

আউটপুট - লোকেশন, যেখানে প্যাটার্ন টেক্সটে আছে

শুরু
  patLen := প্যাটার্ন সাইজ
  strLen := স্ট্রিং সাইজ
  i := 0 থেকে (strLen - patLen) পর্যন্ত, করুন
    j := 0 থেকে patLen পর্যন্ত, করুন
      যদি text[i+j] ≠ pattern[j], তবে
        লুপ ব্রেক করুন
    শেষ
    যদি j == patLen, তবে
      পজিশন i ডিসপ্লে করুন, কারণ সেখানে প্যাটার্ন পাওয়া গেল
  শেষ
শেষ

উদাহরণ

#include<iostream> using namespace std; void naivePatternSearch(string mainString, string pattern, int array[], int *index) { int patLen = pattern.size(); int strLen = mainString.size(); for(int i = 0; i<=(strLen - patLen); i++) { int j; for(j = 0; j<patLen; j++) { //প্যাটার্নের প্রতিটি ক্যারেক্টার চেক করুন যদি ম্যাচ হয় if(mainString[i+j] != pattern[j]) break; } if(j == patLen) { //প্যাটার্ন পাওয়া গেল (*index)++; array[(*index)] = i; } } } int main() { string mainString = "ABAAABCDBBABCDDEBCABC"; string pattern = "ABC"; int locArray[mainString.size()]; int index = -1; naivePatternSearch(mainString, pattern, locArray, &index); for(int i = 0; i <= index; i++) { cout << "Pattern found at position: " << locArray[i]<<endl; } }

আউটপুট

Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18