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

C++ में विशिष्ट प्रतिध्वनि उपस्ट्रिंग्स

मान लीजिए हमारे पास एक स्ट्रिंग S है; हमें S के विशिष्ट गैर-खाली उपस्ट्रिंग्स की संख्या ज्ञात करनी है जिन्हें किसी स्ट्रिंग के साथ स्वयं के संयोजन के रूप में लिखा जा सकता है।

यदि इनपुट "elloelloello" है, तो आउटपुट 5 होगा, क्योंकि कुछ उपस्ट्रिंग्स हैं जैसे "ello", "lloe", "loel", "oell"।

हल करने के चरण

  • prime := 31, m := 10^9 + 7

  • fastPow() फ़ंक्शन परिभाषित करें मॉड्यूलर घातांक के लिए

  • createHashValue() फ़ंक्शन परिभाषित करें स्ट्रिंग का हैश मान बनाने के लिए

  • recalculateHash() फ़ंक्शन परिभाषित करें रोलिंग हैश के लिए

  • मुख्य विधि से: सभी सम लंबाई के लिए, स्लाइडिंग विंडो का उपयोग करके पहले आधे और दूसरे आधे के हैश की तुलना करें, मिलान होने पर सेट में डालें

  • सेट का आकार लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
typedef long long int lli; 
const lli prime = 31; 
const lli m = 1e9 + 7; 

class Solution { 
public: 
    lli fastPow(lli base, lli power) { 
        lli res = 1; 
        while (power > 0) { 
            if (power & 1) { res = res * base; res %= m; } 
            base *= base; base %= m; power >>= 1; 
        } 
        return res; 
    } 
    lli createHashValue(string s, lli n) { 
        lli result = 0; 
        for (lli i = 0; i < n; i++) { 
            result += (lli)(s[i] * fastPow(prime, i)); 
            result %= m; 
        } 
        return result; 
    } 
    lli recalculateHash(char old, char newC, lli oldHash, lli patLength) { 
        lli newHash = oldHash - (lli)old; 
        newHash *= fastPow(prime, m - 2); 
        newHash += ((lli)newC * fastPow(prime, patLength - 1)); 
        newHash %= m; 
        return newHash; 
    } 
    int distinctEchoSubstrings(string text) { 
        int n = text.size(); 
        set<int> ans; 
        for (int i = 2; i <= n; i += 2) { 
            string temp = ""; 
            for (int j = 0; j < i / 2; j++) temp += text[j]; 
            int hash1 = createHashValue(temp, i / 2); 
            temp = ""; 
            for (int j = i / 2; j < i; j++) temp += text[j]; 
            int hash2 = createHashValue(temp, i / 2); 
            for (int s1 = 0, e1 = i / 2, s2 = i / 2, e2 = i; e2 < n; s1++, s2++, e1++, e2++) { 
                if (hash1 == hash2) ans.insert(hash1); 
                hash1 = recalculateHash(text[s1], text[e1], hash1, i / 2); 
                hash2 = recalculateHash(text[s2], text[e2], hash2, i / 2); 
            } 
            if (hash1 == hash2) ans.insert(hash1); 
        } 
        return ans.size(); 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.distinctEchoSubstrings("elloelloello")); 
    return 0; 
}

इनपुट

"elloelloello"

आउटपुट

5
  1. - C++ में 8 से विभाज्य और 3 से नहीं विभाज्य सबस्ट्रिंग्स की संख्या

    0-9 की एक स्ट्रिंग दी गई है। इस समस्या के लिए, हमें उन स्ट्रिंग्स की संख्या की गणना करने की आवश्यकता है जो 8 से विभाज्य हैं और 3 से नहीं। यह एक 2-चरण की समस्या है, और हमें इसे हल करने के लिए एक बार में एक चरण का कोड करना होगा, उदाहरण के लिए इनपुट str = 80 आउटपुट 2 इनपुट str = 7675636788 आउटपुट 15 स

  1. - C++ में पूर्णांकों की स्ट्रिंग में 6 से विभाज्य सबस्ट्रिंग्स की संख्या

    हम एक ऐसी समस्या को देखेंगे जिसमें हमें एक पूर्णांक स्ट्रिंग दी गई है और यह निर्धारित करना है कि पूर्णांक प्रारूप में कितने सबस्ट्रिंग्स 6 से विभाज्य हैं। यह ध्यान दिया जाना चाहिए कि इनपुट संख्याओं (पूर्णांकों) से बनी स्ट्रिंग के रूप में है। फिर भी, विभाज्यता जांच केवल पूर्णांक के रूप में की जाएगी

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की