জেড অ্যালগরিদম

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

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

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

Input:
Main String: “ABAAABCDBBABCDDEBCABC”, Pattern: “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

অ্যালগরিদম

FillZArray (conStr, ZArray)

ইনপুট - conStr হল প্যাটার্ন এবং প্রধান টেক্সটের একত্রিত স্ট্রিং। দীর্ঘতম সম্ভাব্য সাবস্ট্রিং এর সূচী সংরক্ষণ করতে ZArray.

আউটপুট - ভরা ZArray

Begin
   n := length of conStr
   windLeft := 0 and windRight := 0

   for i := 1 to n, do
      if i > windRight, then
         windLeft := i and windRight := i
         while windRight < n AND conStr[windRight-windLeft] =
            conStr[windRight], do
            increase windRight by 1
         done
         ZArray[i] := windRight – windLeft
         decrease windRight by 1
      else
         k := i – windLeft
         if ZArray[k] < windRight – i +1, then
            ZArray[i] := ZArray[k]
         else
            windLeft := i
            while windRight < n AND conStr[windRight-windLeft] =
               conStr[windRight], do
               increase windRight by 1
            done
            ZArray[i] := windRight – windLeft
            decrease windRight by 1
   done
End

zAlgorithm(টেক্সট, প্যাটার্ন)

ইনপুট - মূল পাঠ্য এবং অনুসন্ধানের প্যাটার্ন

আউটপুট - অবস্থান যেখানে প্যাটার্নটি পাওয়া যায়

Begin
   conStr = concatenate pattern + “$” + text
   patLen := length of pattern
   len := conStr length
   fillZArray(conStr, ZArray)

   for i := 0 to len – 1, do
      if ZArray[i] = patLen, then
         print the location i – patLen – 1
   done
End

উদাহরণ

#include<iostream>
using namespace std;

void fillZArray(string conStr, int zArr[]) {
   int n = conStr.size();
   int windLeft, windRight, k;
   windLeft = windRight = 0;    //initially window size is 0

   for(int i = 1; i < n; i++) {
      if(i > windRight) {
         windLeft = windRight = i;     //window size is 0 but position to i
         while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
            windRight++;     //extend the right bound of window
         }
         zArr[i] = windRight-windLeft;
         windRight--;
      }else {
         k = i-windLeft;
         if(zArr[k] < windRight-i+1)
            zArr[i] = zArr[k];    //when kth item less than remaining interval
         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;    //concat with special character
   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