Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में Z एल्गोरिदम (रैखिक समय पैटर्न खोज एल्गोरिदम)


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 पर पाया गया
  1. C/C++ में बर्कले का एल्गोरिथ्म C/C++ में बर्कले का एल्गोरिथ्म

    बर्कले का एल्गोरिथ्म वितरित प्रणालियों में क्लॉक सिंक्रोनाइज़ेशन के लिए उपयोग किया जाने वाला एक एल्गोरिथ्म है। यह एल्गोरिथ्म उन मामलों में उपयोग किया जाता है जब वितरित नेटवर्क के कुछ या सभी सिस्टम में निम्नलिखित समस्याएं होती हैं: A. मशीन के पास सटीक समय स्रोत नहीं है। B. नेटवर्क या मशीन के पास UTC

  1. - C++ में स्ट्रिंग को वेव पैटर्न में प्रिंट करना

    इस समस्या में, हमें एक स्ट्रिंग और एक पूर्णांक n दिया गया है। हमारा कार्य दी गई स्ट्रिंग को n लाइनों के वेव पैटर्न में प्रिंट करना है। उदाहरण Input: Tutorial n = 3 Output: T r U o i s t l वेव पैटर्न स्ट्रिंग के प्रत्येक कैरेक्टर को एक-एक करके अगली लाइन में और अगले

  1. - C++ प्रोग्राम: पैटर्न खोज के लिए फाइनाइट ऑटोमेटा एल्गोरिदम

    इस लेख में, हम पैटर्न खोज के लिए फाइनाइट ऑटोमेटा एल्गोरिदम को निष्पादित करने के लिए एक प्रोग्राम पर चर्चा करेंगे। हमें एक टेक्स्ट[0...n-1] और एक पैटर्न[0...m-1] प्रदान किया गया है। हमें पैटर्न[] की टेक्स्ट[] में सभी घटनाओं को खोजना होगा। इसके लिए हम टेक्स्ट[] को पूर्व-प्रसंस्कृत करेंगे और इसे दर्शा