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

C++ प्रोग्राम: सीक्वेंस के सेट में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजना


यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो एक सेट ऑफ सीक्वेंस में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजता है।

एल्गोरिदम

Begin
    स्ट्रिंग्स की ऐरे को इनपुट के रूप में लें।
    function matchedPrefixtill(): स्ट्रिंग s1 और s2 के बीच मैच्ड प्रीफिक्स खोजें:
        n1 = स्ट्रिंग s1 की लंबाई स्टोर करें।
        n2 = स्ट्रिंग s2 की लंबाई स्टोर करें।
        for i = 0, j = 0 से i <= n1 - 1 && j <= n2 - 1 तक
            यदि s1[i] != s2[j]
                ब्रेक
            result.push_back(s1[i])
        return result
    End
    
    function matchedPrefix(): स्ट्रिंग्स की ऐरे से सबसे लंबा मैच्ड प्रीफिक्स लौटाता है:
        for int i = 1 से n - 1 तक
            pre = matchedPrefixtill(pre, a[i])
        return pre.
    End
End

उदाहरण

#include <bits/stdc++.h>
using namespace std;

string matchedPrefixtill(string s1, string s2) {
    string res;
    int n1 = s1.length(); // स्ट्रिंग s1 की लंबाई स्टोर करें
    int n2 = s2.length(); // स्ट्रिंग s2 की लंबाई स्टोर करें
    
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
        if (s1[i] != s2[j])
            break;
        res.push_back(s1[i]);
    }
    return (res);
}

string matchedPrefix(string a[], int n) {
    string pre = a[0];
    for (int i = 1; i <= n - 1; i++)
        pre = matchedPrefixtill(pre, a[i]);
    return (pre);
}

int main() {
    string a[] = {"Tutorialspoint", "Tutor", "Tutorials"}; // इनपुट लेना
    int n = sizeof(a) / sizeof(a[0]);
    string res = matchedPrefix(a, n);
    
    if (res.length())
        cout << "Longest common subsequence is matched - " << res.c_str();
    else
        cout << "No matched prefix";
    
    return (0);
}

आउटपुट

Longest common subsequence is matched - Tutor

नोट: यह प्रोग्राम वास्तव में लॉन्गेस्ट कॉमन प्रीफिक्स (LCP) खोजता है, लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) नहीं। LCS के लिए डायनामिक प्रोग्रामिंग की आवश्यकता होती है (O(n*m) प्रति जोड़ी)। LCP केवल शुरुआत से मेल खाने वाले कैरेक्टर्स की जांच करता है, जबकि LCS कहीं भी मेल खाने वाले कैरेक्टर्स को अनुमति देता है। शीर्षक भ्रामक है - कोड प्रीफिक्स के लिए काम करता है, सबसीक्वेंस के लिए नहीं।

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

    एक स्ट्रिंग एक एक-आयामी कैरेक्टर सरणी है जो नल कैरेक्टर द्वारा समाप्त होती है। स्ट्रिंग में कैरेक्टर्स की फ्रीक्वेंसी वह संख्या है जितनी बार वे स्ट्रिंग में आते हैं। उदाहरण के लिए: स्ट्रिंग: Football is a sport उपरोक्त स्ट्रिंग में वर्ण o की फ्रीक्वेंसी 3 है किसी विशेष वर्ण की फ्रीक्वेंसी खोजने का ए

  1. - C++ में स्ट्रिंग की लंबाई खोजने का प्रोग्राम

    एक स्ट्रिंग एक एक-आयामी कैरेक्टर सरणी है जो नल कैरेक्टर द्वारा समाप्त होती है। स्ट्रिंग की लंबाई नल कैरेक्टर से पहले स्ट्रिंग में कैरेक्टर्स की संख्या होती है। उदाहरण के लिए। char str[] = “The sky is blue”; उपरोक्त स्ट्रिंग में कैरेक्टर्स की संख्या = 15 स्ट्रिंग की लंबाई खोजने का एक प्रो

  1. - स्ट्रिंग के सभी सबसेट्स खोजने के लिए Java प्रोग्राम

    इस लेख में, हम समझेंगे कि स्ट्रिंग के सभी सबसेट्स कैसे खोजें। String एक डेटा प्रकार है जिसमें एक या अधिक कैरेक्टर्स होते हैं और यह डबल कोट्स ( ) में संलग्न होता है। स्ट्रिंग का एक भाग या उपसमूह सबस्ट्रिंग कहलाता है। नीचे इसका प्रदर्शन है: मान लीजिए हमारा इनपुट है: स्ट्रिंग परिभाषित है: JVM वांछि