Z एल्गोरिदम का उपयोग किसी स्ट्रिंग में पैटर्न की घटनाओं को रैखिक समय में खोजने के लिए किया जाता है। यदि स्ट्रिंग की लंबाई n है और खोजे जाने वाले पैटर्न का आकार m है, तो इसे हल करने में लगा समय O(m+n) क्रम का होगा।
Z-एल्गोरिदम पैटर्न की घटनाओं को खोजने के लिए एक Z ऐरे का उपयोग करता है।
Z ऐरे
यह स्ट्रिंग के समान लंबाई का एक ऐरे है। Z-ऐरे का प्रत्येक तत्व स्ट्रिंग के सबसे लंबे उपस्ट्रिंग की लंबाई से मिलकर बनता है जो इंडेक्स i से शुरू होता है और जिसे स्ट्रिंग के प्रीफिक्स के रूप में उपयोग किया जा सकता है।
एल्गोरिदम
इस एल्गोरिदम में, हमें लंबाई 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] निम्न चरणों का उपयोग करके गणना करें:
चरण 1: यदि i > R, तो कोई बड़ा प्रीफिक्स-उपस्ट्रिंग संभव नहीं है। इसलिए, हम S[0] की तुलना S[i] से करके नया अंतराल गणना करेंगे, यानी इंडेक्स 0 से शुरू होने वाली स्ट्रिंग की तुलना इंडेक्स i से शुरू होने वाली उपस्ट्रिंग से करेंगे। और Z[i] = R - L + 1 का उपयोग करके Z[i] ज्ञात करेंगे।
चरण 2: अन्यथा यदि i ≤ R, तो [L, R] को i तक बढ़ाया जा सकता है। k = i-L के लिए, Z[i] ≥ min(Z[k], R-i+1)।
चरण 2.1: यदि Z[k] < R-i+1, तो i से शुरू होने वाला कोई लंबा प्रीफिक्स उपस्ट्रिंग मौजूद नहीं है।
चरण 2.2: यदि Z[k] ≥ R-i+1, तो एक लंबा उपस्ट्रिंग हो सकता है। इसलिए, हम L = i बदलकर और S[R+1] से मिलान करके R को बदलकर [L, 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 << "पैटर्न '" << pattern << "' स्ट्रिंग '" << str << "' में इंडेक्स पर पाया गया: ";
zAlgorithm(str, pattern);
return 0;
}
आउटपुट
पैटर्न ' tutorial ' स्ट्रिंग 'Hello! Welcome To tutorials Point programming tutorial ' में इंडेक्स 18 46 पर पाया गया