C++-এ Z অ্যালগরিদম (লিনিয়ার টাইম প্যাটার্ন সার্চিং অ্যালগরিদম)

Z অ্যালগরিদম একটি স্ট্রিং-এর মধ্যে প্যাটার্ন খুঁজে বের করার জন্য ব্যবহৃত হয় যা লিনিয়ার টাইমে কাজ করে। যদি স্ট্রিং-এর দৈর্ঘ্য n এবং প্যাটার্নের আকার m হয়, তবে সময় জটিলতা হবে O(m+n)।

Z-অ্যালগরিদম প্যাটার্ন খুঁজে বের করার জন্য Z অ্যারে ব্যবহার করে।

Z অ্যারে

এটি স্ট্রিং-এর সমান দৈর্ঘ্যের একটি অ্যারে। Z-অ্যারের প্রতিটি উপাদান স্ট্রিং-এর সেই সূচক থেকে শুরু হওয়া সবচেয়ে বড় সাবস্ট্রিং-এর দৈর্ঘ্য ধারণ করে যা স্ট্রিং-এর প্রিফিক্স ও হতে পারে।

অ্যালগরিদম

এই অ্যালগরিদমে, আমাদের দৈর্ঘ্য n এর একটি স্ট্রিং S এবং দৈর্ঘ্য m এর একটি প্যাটার্ন p দেওয়া থাকে।

আমরা একটি Z অ্যারে তৈরি করব। এরপর অ্যালগরিদমটি স্ট্রিং-এর সব ক্যারেক্টারের জন্য i = 1 থেকে n-1 পর্যন্ত লুপ চালাবে। এখন, আমরা একটি সাবস্ট্রিং s[L-R] তৈরি করব যা একটি প্রিফিক্স সাবস্ট্রিং যাতে 1 ≤ L ≤ i ≤ R থাকে।

i-1 এর জন্য সঠিক ইন্টারভাল [L, R] এবং i-1 পর্যন্ত সব Z মান ব্যবহার করে Z[i] এবং নতুন ইন্টারভাল [L, R] নিচের ধাপগুলো অনুসরণ করে বের করব:

ধাপ ১: যদি i > R হয়, তবে বড় প্রিফিক্স-সাবস্ট্রিং সম্ভব নয়। তখন আমরা S[0] এবং S[i] তুলনা করে নতুন ইন্টারভাল বের করব, অর্থাৎ সূচক ০ থেকে শুরু হওয়া স্ট্রিং এবং সূচক i থেকে শুরু হওয়া সাবস্ট্রিং তুলনা করব। এবং Z[i] = R - L + 1 সূত্রে মান বের করব। 
ধাপ ২: অন্যদিকে, যদি i ≤ R হয়, তবে [L, R] কে i পর্যন্ত প্রসারিত করা যাবে। k = i-L এর জন্য, Z[i] ≥ min(Z[k], R-i+1)।
  ধাপ ২.১: যদি Z[k] < R-i+1 হয়, তবে s[i] থেকে শুরু হওয়া আরো বড় প্রিফিক্স সাবস্ট্রিং নেই।
  ধাপ ২.২: যদি Z[k] ≥ R-i+1 হয়, তবে আরও বড় সাবস্ট্রিং থাকতে পারে। তখন আমরা [L, R] আপডেট করব L = i সেট করে এবং S[R+1] থেকে মিলিয়ে R পরিবর্তন করব।

এই প্রক্রিয়া একই ইটারেশনে (শুধু একবার লুপ চালিয়ে) সব Z মান বের করে দেয়।

উদাহরণ

অ্যালগরিদমের বাস্তবায়নের প্রোগ্রাম:

#include<iostream> 
using namespace std; 

void createZarray(string str, int Z[]) {
    int n = str.length();
    int L, R, k;
    L = R = 0;
    for (int i = 1; i < n; ++i) {
        if (i > R) {
            L = R = i;
            while (R < n && str[R-L] == str[R])
                R++;
            Z[i] = R-L;
            R--;
        } else {
            k = i-L;
            if (Z[k] < R-i+1)
                Z[i] = Z[k];
            else {
                L = i;
                while (R < n && str[R-L] == str[R])
                    R++;
                Z[i] = R-L;
                R--;
            }
        }
    }
}

void zAlgorithm(string text, string pattern) {
    string str = pattern + "$" + text;
    int len = str.length();
    int Z[len];
    createZarray(str, Z);
    for (int i = 0; i < len; ++i) {
        if (Z[i] == pattern.length())
            cout << (i - pattern.length() - 1) << "\t";
    }
}

int main() {
    string str = "Hello! Welcome To tutorials Point programming tutorial";
    string pattern = "tutorial";
    cout << "The pattern '" << pattern << "' is found in the string '" << str << "' at index \t";
    zAlgorithm(str, pattern);
    return 0;
}

আউটপুট

The pattern ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46