Z অ্যালগরিদম রৈখিক সময়ে একটি স্ট্রিং-এ একটি প্যাটার্নের উপস্থিতি খুঁজে পেতে ব্যবহৃত হয়। ধরুন যদি স্ট্রিংয়ের দৈর্ঘ্য n হয় এবং যে প্যাটার্নটি অনুসন্ধান করা হবে তার আকার m হয়, তাহলে সমাধান করতে যে সময় লাগবে তা হবে O(m+n) .
z-অ্যালগরিদম একটি প্যাটার্নের উপস্থিতি খুঁজে পেতে একটি Z অ্যারে ব্যবহার করে।
Z অ্যারে
৷এটি স্ট্রিং হিসাবে একই দৈর্ঘ্যের একটি অ্যারে। z-অ্যারের প্রতিটি উপাদান I থেকে শুরু করে স্ট্রিংয়ের দীর্ঘতম সাবস্ট্রিংয়ের দৈর্ঘ্য নিয়ে গঠিত যা স্ট্রিংয়েরই একটি উপসর্গ হিসাবে ব্যবহার করা যেতে পারে।
অ্যালগরিদম
এই অ্যালগরিদমে, আমাদের এন দৈর্ঘ্যের একটি স্ট্রিং এবং m দৈর্ঘ্যের p অনুসন্ধান করা প্যাটার্ন দেওয়া হয়েছে।
আমরা একটি z অ্যারে তৈরি করব। এখন, i =1 থেকে n-1 সহ স্ট্রিংয়ের সমস্ত অক্ষরের অ্যালগরিদম লুপ করে। এখন, আমরা একটি সাবস্ট্রিং s[L-R] তৈরি করব যা একটি প্রিফিক্স সাবস্ট্রিং যেমন 1 ≤ L ≤ I ≤ R.
এখন, i-1 এবং i-1 পর্যন্ত সমস্ত z মানগুলির জন্য সাবস্ট্রিং [L, R] তৈরি করার জন্য একটি সঠিক ব্যবধানের জন্য। নিম্নলিখিত ধাপগুলি ব্যবহার করে z[i] এবং নতুন ব্যবধান [L, R] গণনা করুন −
Step1: if i > R, no larger prefix-substring is possible. So, we will compute new interval bt comparing S[0] to S[i] i.e. string starting from index 0 i.e. from start with substring starting from index i. And find z[i] using z[i] = R - L + 1. Step 2: Else if, i ≤ R, [L, R] can be extended to i. For k = i-L, z[i] ≥ min(Z[k], R-i+1). Step 2.1: If, Z[k] < R-i+1, no longer prefix substring s[i] exist. Step 2.2: If Z[k] ≥ R-i+1, then there can be a longer substring. So, we will update [L, R] by changing L = i and changing R by matching from S[R+1].
এই প্রক্রিয়াটি একটি একক পুনরাবৃত্তিতে সমস্ত 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 patter ' "<<pattern<<" ' is found in the string '"<<str<<" ' at index \t";
zAlgorithm(str, pattern);
return 0;
} আউটপুট
The patter ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46-এ 'পয়েন্ট প্রোগ্রামিং টিউটোরিয়াল'-এ স্বাগতম
