Z एल्गोरिथम रैखिक समय में एक स्ट्रिंग में एक पैटर्न की घटना को खोजने के लिए प्रयोग किया जाता है। मान लीजिए यदि स्ट्रिंग की लंबाई n है और खोजे जाने वाले पैटर्न का आकार m है, तो हल करने में लगने वाला समय O(m+n) के क्रम का होगा। ।
z-एल्गोरिदम एक पैटर्न की घटना को खोजने के लिए एक Z सरणी का उपयोग करता है।
Z सरणी
यह स्ट्रिंग के समान लंबाई की एक सरणी है। जेड-सरणी के प्रत्येक तत्व में I से शुरू होने वाली स्ट्रिंग की सबसे लंबी सबस्ट्रिंग की लंबाई होती है जिसे स्ट्रिंग के उपसर्ग के रूप में उपयोग किया जा सकता है।
एल्गोरिदम
इस एल्गोरिथम में, हमें लंबाई n की एक स्ट्रिंग S और लंबाई m की खोज करने के लिए पैटर्न दिया गया है।
हम एक z सरणी बनाएंगे। अब, एल्गोरिथ्म स्ट्रिंग के सभी वर्णों को i =1 से n-1 तक लूप करता है। अब, हम एक सबस्ट्रिंग s[L-R] बनाएंगे जो एक उपसर्ग सबस्ट्रिंग है जैसे कि 1 ≤ L ≤ I ≤ R.
अब, i-1 के लिए सबस्ट्रिंग [L, R] और i-1 तक के सभी z मानों को बनाने के लिए एक सही अंतराल के लिए। निम्नलिखित चरणों का उपयोग करके 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