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

C++ में रैपराउंड स्ट्रिंग में यूनिक सबस्ट्रिंग्स


मान लीजिए स्ट्रिंग s "abcdefghijklmnopqrstuvwxyz" की अनंत रैपराउंड स्ट्रिंग है, इसलिए s का मान ऐसा दिखेगा: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."।

अब हमारे पास एक और स्ट्रिंग p है। हमारा काम यह पता लगाना है कि p के कितने यूनिक नॉन-एम्प्टी सबस्ट्रिंग्स s में मौजूद हैं। विशेष रूप से, हमारा इनपुट स्ट्रिंग p है और हमें p के विभिन्न नॉन-एम्प्टी सबस्ट्रिंग्स की संख्या आउटपुट करनी है जो स्ट्रिंग s में हैं।

उदाहरण के लिए, अगर इनपुट "zab" है तो आउटपुट 6 होगा। "zab" स्ट्रिंग के 6 सबस्ट्रिंग्स "z", "a", "b", "za", "ab", "zab" स्ट्रिंग s में हैं।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

  • साइज 26 का एक ऐरे dp बनाएं, x := 0 सेट करें

  • i को 0 से p के साइज तक लूप करें:

    • अगर i > 0 और (p[i] - p[i-1] 1 है या p[i-1] - p[i] 25 है), तो x को 1 से बढ़ाएं, अन्यथा x := 1 सेट करें

    • dp[p[i] - 'a' का ASCII] := max(x, dp[p[i] - 'a' का ASCII])

  • ret := 0

  • i को 0 से 25 तक लूप करें:

    • ret := ret + dp[i]

  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

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

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector <int> dp(26);
        int x = 0;
        for(int i = 0; i < p.size(); i++){
            if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
                x++;
            }
            else x = 1;
            dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
        }
        int ret = 0;
        for(int i = 0; i < 26; i++){
            ret += dp[i];
        }
        return ret;
    }
};

int main(){
    Solution ob;
    cout << (ob.findSubstringInWraproundString("zab"));
}

इनपुट

"zab"

आउटपुट

6

  1. - C++ कोड: संख्यात्मक स्ट्रिंग के सम सबस्ट्रिंग की गणना करें

    मान लीजिए हमारे पास n अंकों का एक स्ट्रिंग S है। S का एक सबस्ट्रिंग सम कहा जाता है यदि इस स्ट्रिंग द्वारा दर्शाई गई संख्या भी सम है। हमें S के सम सबस्ट्रिंग की संख्या ढूंढनी है।उदाहरण के लिए, यदि इनपुट S = 1234 है, तो आउटपुट 6 होगा, क्योंकि सबस्ट्रिंग हैं 2, 4, 12, 34, 234, 1234।इसे हल करने के लिए,

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

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

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

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