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

C++ प्रोग्राम: वैगनर-फिशर एल्गोरिदम से ऑनलाइन स्ट्रिंग मैचिंग इम्प्लीमेंट करना


इस सेक्शन में हम देखेंगे कि वैगनर-फिशर एल्गोरिदम का उपयोग करके दो स्ट्रिंग्स की तुलना कैसे करें। इस एल्गोरिदम का उपयोग करके, हम पता लगा सकते हैं कि उन स्ट्रिंग्स को मैच करने के लिए न्यूनतम कितने परिवर्तनों की आवश्यकता है।

यह एक डायनामिक प्रोग्रामिंग दृष्टिकोण है। यहां हम दो स्ट्रिंग्स से लेवेनश्टाइन दूरी मापते हैं।

इनपुट: दो स्ट्रिंग्स "Support" & "Suppose"
आउटपुट: आवश्यक न्यूनतम परिवर्तनों की संख्या: 2

एल्गोरिदम

Wagner_Fisher(str1, str2)

इनपुट: दो स्ट्रिंग्स str1 और str2
आउटपुट: न्यूनतम परिवर्तनों की संख्या

l1 := str1 की लंबाई, और l2 = str2 की लंबाई
(l1 * l2) ऑर्डर का मैट्रिक्स d परिभाषित करें
d की पहली पंक्ति को 0 से l1-1 तक नंबर्स से भरें, और पहली कॉलम को 0 से l2-1 तक नंबर्स से भरें
j को 1 से l1 की रेंज में, करें
    i को 1 से l2 की रेंज में, करें
        यदि str1[i-1] = str2[j-1], तो
            tracker := 0
        अन्यथा
            tracker := 1
        temp := d[i-1, j] + 1 और d[i, j-1] + 1 का न्यूनतम
        d[i, j] = temp और (d[i-1, j-1] + tracker) का न्यूनतम
    किया
किया
d[l2, l1] लौटाएं

उदाहरण कोड

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int d[100][100];

int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int i, j, str1_len, str2_len, temp, tracker;
    string str1 = "Support";
    string str2 = "Suppose";
    str1_len = str1.length();
    str2_len = str2.length();
    
    for (i = 0; i <= str1_len; i++)
        d[0][i] = i;
    for (j = 0; j <= str2_len; j++)
        d[j][0] = j;
    
    for (j = 1; j <= str1_len; j++) {
        for (i = 1; i <= str2_len; i++) {
            if (str1[i - 1] == str2[j - 1]) {
                tracker = 0;
            } else {
                tracker = 1;
            }
            temp = min((d[i - 1][j] + 1), (d[i][j - 1] + 1));
            d[i][j] = min(temp, (d[i - 1][j - 1] + tracker));
        }
    }
    cout << "The Levenshtein distance " << d[str2_len][str1_len];
}

आउटपुट:

The Levenshtein distance 2

  1. - C++ में स्ट्रिंग ट्रांसफॉर्मेशन के लिए इन-प्लेस एल्गोरिदम

    एक दी गई स्ट्रिंग के लिए, सभी सम स्थित वाले तत्वों को स्ट्रिंग के अंत में स्थानांतरित करें। तत्वों को स्थानांतरित करते समय, सभी सम स्थित और विषम स्थित तत्वों का सापेक्ष क्रम समान रखें।उदाहरण के लिए, यदि दी गई स्ट्रिंग a1b2c3d4e5f6g7h8i9j1k2l3m4 है, तो इसे abcdefghijklm1234567891234 में इन-प्लेस और O

  1. ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम के लिए C++ प्रोग्राम ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम के लिए C++ प्रोग्राम

    पेज नंबर और पेज साइज़ दिए गए हैं; कार्य ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम का उपयोग करके मेमोरी ब्लॉक को पेज में आवंटित करते समय हिट्स और मिस की संख्या ढूंढना है। ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम क्या है? ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम एक पेज रिप्लेसमेंट एल्गोरिदम है। एक पेज रिप्लेसमेंट एल्गोरि

  1. - C++ प्रोग्राम: फिशर-येट्स एल्गोरिदम से ऐरे शफलिंग

    फिशर-येट्स एल्गोरिदम फिशर-येट्स एल्गोरिदम ऐरे तत्वों का यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, यानी यह ऐरे के सभी तत्वों को निष्पक्ष रूप से शफल करता है। सभी क्रमपरिवर्तन समान रूप से संभावित होते हैं। C++ प्रोग्राम उदाहरण #include <iostream> #include <cstdlib> #include <ctime> us