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

C++ में फाइनाइट स्टेट ऑटोमेटन आधारित खोज


यह फाइनाइट स्टेट ऑटोमेटन आधारित खोज करने के लिए एक C++ प्रोग्राम है। एक ऑटोमेटन जिसमें राज्यों की एक सीमित संख्या होती है, उसे फाइनाइट ऑटोमेटन कहा जाता है। यहां, एक टेक्स्ट दिया गया है text[0...t-1] और एक पैटर्न p[0...p-1] भी दिया गया है। हमें टेक्स्ट में पैटर्न ढूंढना है और उसकी सभी घटनाओं को संबंधित इंडेक्स पर प्रिंट करना है।

एल्गोरिदम

Begin
    Function void transitiontable():
        1) पहली पंक्ति में प्रविष्टियां डालें और इसे भरें। पहली पंक्ति में सभी प्रविष्टियां हमेशा 0 होती हैं सिवाय p[0] कैरेक्टर के लिए प्रविष्टि के। p[0] के लिए हमें हमेशा स्टेट 1 पर जाने की आवश्यकता होती है।
        2) longestprefixsuffix को 0 के रूप में इनिशियलाइज़ करें।
        3) i = 1 से P तक। (यहां P पैटर्न की लंबाई है)
            a) इंडेक्स longestprefixsuffix के बराबर पंक्ति से प्रविष्टियां कॉपी करें।
            b) p[i] कैरेक्टर के लिए प्रविष्टि को i+1 पर अपडेट करें।
            c) longestprefixsuffix = TF[lps][pat[i]] अपडेट करें
               जहां TT 2D ऐरे है।
End

उदाहरण

#include <iostream>
#include <cstring>
#define NO_OF_CHARS 512
using namespace std;

// दिए गए पैटर्न के लिए फाइनाइट ऑटोमेटा को दर्शाने वाली TF टेबल बनाता है
void transitiontable(char *p, int P, int TT[][NO_OF_CHARS]) {
    int i, longestprefixsuffix = 0, y;
    
    // पहली पंक्ति में प्रविष्टियां डालें
    for(y = 0; y < NO_OF_CHARS; y++)
        TT[0][y] = 0;
    TT[0][p[0]] = 1;
    
    // अन्य पंक्तियों में प्रविष्टियां डालें
    for(i = 1; i <= P; i++) { // इंडेक्स longestprefixsuffix पर पंक्ति से मान कॉपी करें
        for(y = 0; y < NO_OF_CHARS; y++)
            TT[i][y] = TT[longestprefixsuffix][y];
        
        // प्रविष्टि अपडेट करें
        TT[i][p[i]] = i + 1;
        
        // अगली पंक्ति के लिए lps अपडेट करें
        if(i < P)
            longestprefixsuffix = TT[longestprefixsuffix][p[i]]; // TT वह 2D ऐरे है जिसे बनाया जा रहा है
    }
}

// टेक्स्ट में पैटर्न की सभी घटनाओं को प्रिंट करता है
void patternsearch(char *p, char *t) {
    int P = strlen(p);
    int T = strlen(t);
    int TT[P+1][NO_OF_CHARS];
    transitiontable(p, P, TT);
    
    // FA पर टेक्स्ट प्रोसेस करें
    int i, j = 0;
    for(i = 0; i < T; i++) {
        j = TT[j][t[i]];
        if(j == P) {
            cout << "\n pattern is found at index: " << i-P+1;
        }
    }
}

int main() {
    char *text = "AABAA ABBAACCDD CCDDAABAA"; // टेक्स्ट को इनपुट के रूप में लें
    char *pattern = "AABAA"; // पैटर्न को इनपुट के रूप में लें
    patternsearch(pattern, text);
    return 0;
}

आउटपुट

pattern is found at index: 0
pattern is found at index: 20

फाइनाइट ऑटोमेटन आधारित पैटर्न खोज (KMP एल्गोरिदम से संबंधित) टेक्स्ट को O(n) समय में प्रीप्रोसेस्ड ट्रांजिशन टेबल के साथ प्रोसेस करती है। ट्रांजिशन टेबल बनाने में O(m * अल्फाबेट_साइज) समय लगता है। यह तब कुशल होता है जब एक ही पैटर्न को कई टेक्स्ट्स में खोजा जाता है या जब अल्फाबेट आकार छोटा होता है।

  1. C++ में बाइनरी खोज प्रोग्राम C++ में बाइनरी खोज प्रोग्राम

    बाइनरी खोज क्या है? बाइनरी खोज (आधा-अंतराल खोज) एक खोज एल्गोरिदम है जो क्रमबद्ध सरणी में लक्ष्य मान की स्थिति ढूंढता है। यह लक्ष्य मान की तुलना मध्य तत्व से करता है और खोज स्थान को आधा कर देता है। मुख्य बिंदु केवल क्रमबद्ध सरणी पर काम करता है समय जटिलता: O(log n) दुनिया के सभी नाम क्रमबद्ध हों तो

  1. C++ प्रोग्राम: बाइनरी सर्च ट्री पर लेफ्ट रोटेशन करना C++ प्रोग्राम: बाइनरी सर्च ट्री पर लेफ्ट रोटेशन करना

    एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित दो गुण होते हैं - एक नोड का राइट सब-ट्री उसके पैरेंट नोड की कुंजी से अधिक सभी कुंजियों को रखता है। एक नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की कुंजी से कम सभी कुंजियों को रखता है। प्रत्येक नोड में दो से अधिक चाइल्ड नहीं हो

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

    मैट्रिक्स संख्याओं का एक आयताकार सरणी है जो पंक्तियों और कॉलम के रूप में व्यवस्थित होता है। मैट्रिक्स का एक उदाहरण निम्नलिखित है। एक 3*2 मैट्रिक्स में 3 पंक्तियाँ और 2 कॉलम होते हैं जैसा कि नीचे दिखाया गया है: 8 1 4 9 5 6 मैट्रिक्स गुणा करने का एक प्रोग्राम निम्नलिखित है। उदाहरण #include<iostream