Z অ্যালগরিদম

এই অ্যালগরিদমের নাম Z অ্যালগরিদম কারণ, এই অ্যালগরিদমে আমাদের একটি Z অ্যারে তৈরি করতে হয়। Z অ্যারেতে আকার টেক্সটের আকারের সমান। এই অ্যারেটি মূল স্ট্রিংয়ের বর্তমান ক্যারেক্টার থেকে শুরু হওয়া লংগেস্ট পসিবল সাবস্ট্রিংয়ের দৈর্ঘ্য স্টোর করতে ব্যবহৃত হয়। প্রথমে, প্যাটার্ন এবং মেইন টেক্সট একটি স্পেশাল সিম্বল দিয়ে কনক্যাটেনেট করা হয় যা টেক্সট এবং প্যাটার্নে নেই। যদি P হয় প্যাটার্ন এবং T হয় মেইন টেক্সট, তবে কনক্যাটেনেশনের পর সেটি হবে P$T (ধরে নেওয়া হয় $ P এবং T-তে নেই)।

এই অ্যালগরিদমের জন্য, টাইম কমপ্লেক্সিটি O(m+n) যেখানে m হলো প্যাটার্নের দৈর্ঘ্য এবং n হলো মেইন স্ট্রিংয়ের দৈর্ঘ্য।

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

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

অ্যালগরিদম

fillZArray(conStr, ZArray)

ইনপুট - conStr হলো প্যাটার্ন এবং মেইন টেক্সটের কনক্যাটেনেটেড স্ট্রিং। ZArray লংগেস্ট পসিবল সাবস্ট্রিংয়ের ইনডেক্স স্টোর করতে।

আউটপুট - ভরা हुआ ZArray

শুরু
  n := conStr-এর দৈর্ঘ্য
  windLeft := 0 এবং windRight := 0
  i := 1 থেকে n পর্যন্ত, করুন
    যদি i > windRight, তবে
      windLeft := i এবং windRight := i
      যতক্ষণ windRight < n AND conStr[windRight-windLeft] = conStr[windRight], করুন
        windRight 1 বাড়ান
      শেষ
      ZArray[i] := windRight - windLeft
      windRight 1 কমান
    অন্যথায়
      k := i - windLeft
      যদি ZArray[k] < windRight - i + 1, তবে
        ZArray[i] := ZArray[k]
      অন্যথায়
        windLeft := i
        যতক্ষণ windRight < n AND conStr[windRight-windLeft] = conStr[windRight], করুন
          windRight 1 বাড়ান
        শেষ
        ZArray[i] := windRight - windLeft
        windRight 1 কমান
    শেষ
  শেষ
শেষ

zAlgorithm(text, pattern)

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

আউটপুট - প্যাটার্ন খুঁজে পাওয়া লোকেশন

শুরু
  conStr = প্যাটার্ন + "$" + টেক্সট কনক্যাটেনেট করুন
  patLen := প্যাটার্নের দৈর্ঘ্য
  len := conStr দৈর্ঘ্য
  fillZArray(conStr, ZArray)
  i := 0 থেকে len - 1 পর্যন্ত, করুন
    যদি ZArray[i] = patLen, তবে
      লোকেশন i - patLen - 1 প্রিন্ট করুন
  শেষ
শেষ

উদাহরণ

#include<iostream> using namespace std; void fillZArray(string conStr, int zArr[]) { int n = conStr.size(); int windLeft, windRight, k; windLeft = windRight = 0; //প্রাথমিক উইন্ডো আকার 0 for(int i = 1; i < n; i++) { if(i > windRight) { windLeft = windRight = i; //উইন্ডো আকার 0 কিন্তু পজিশন i-তে while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) { windRight++; //উইন্ডোর ডানে বাউন্ড এক্সটেন্ড করুন } zArr[i] = windRight-windLeft; windRight--; }else { k = i-windLeft; if(zArr[k] < windRight-i+1) zArr[i] = zArr[k]; //যখন k-তম আইটেম রিমেইনিং ইন্টারভ্যাল থেকে কম else { windLeft = i; while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) { windRight++; } zArr[i] = windRight - windLeft; windRight--; } } } } void zAlgorithm(string mainString, string pattern, int array[], int *index) { string concatedStr = pattern + "$" + mainString; //স্পেশাল ক্যারেক্টার দিয়ে কনক্যাট int patLen = pattern.size(); int len = concatedStr.size(); int zArr[len]; fillZArray(concatedStr, zArr); for(int i = 0; i<len; i++) { if(zArr[i] == patLen) { (*index)++; array[(*index)] = i - patLen -1; } } } int main() { string mainString = "ABAAABCDBBABCDDEBCABC"; string pattern = "ABC"; int locArray[mainString.size()]; int index = -1; zAlgorithm(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