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

पुनरावृत्तियों की गिनती - C++


मान लीजिए हमारे पास दो गैर-खाली स्ट्रिंग्स s1 और s2 हैं (अधिकतम 100 वर्ण) और दो संख्याएँ n1 और n2 दोनों 0 से 10^6 की सीमा में हैं। अब मान लीजिए स्ट्रिंग्स S1 और S2, जहां S1=[s1,n1] और S2=[s2,n2]।

S = [s,n] वह स्ट्रिंग S को परिभाषित करता है जिसमें n जुड़ी हुई स्ट्रिंग्स s होती हैं। उदाहरण के लिए, ["ab", 4] ="abababab"।

दूसरी ओर, हम यह भी परिभाषित कर सकते हैं कि स्ट्रिंग s1 को स्ट्रिंग s2 से प्राप्त किया जा सकता है यदि हम s2 से कुछ वर्ण हटाते हैं ताकि यह s1 बन जाए। तो, "abc" को "abdbec" से परिभाषा के आधार पर प्राप्त किया जा सकता है, लेकिन इसे "acbbe" से प्राप्त नहीं किया जा सकता।

हमें अधिकतम पूर्णांक M ढूंढना है जैसे कि [S2,M] को S1 से प्राप्त किया जा सके।

तो, यदि इनपुट s1="acb", n1=4, s2="ab", n2=2 है, तो आउटपुट 2 होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • s2 में प्रत्येक वर्ण c के लिए

    • यदि c, s1 में नहीं है, तो −

      • 0 लौटाएं

  • p1 := 0, p2 := 0, mark := 0

  • जब तक p1, s1 के आकार से कम है, करें −

    • c := s2[p2 mod s2 का आकार]

    • जब तक (s1[p1 mod s1 का आकार] c के बराबर नहीं है और p1, s1 के आकार * n1 से कम है), करें −

      • (p1 को 1 से बढ़ाएं)

    • (p2 को 1 से बढ़ाएं)

    • (p1 को 1 से बढ़ाएं)

    • यदि p2 mod s2 का आकार 0 के समान है, तो −

      • यदि p2, s2 के आकार के समान है, तो −

        • mark := p1

      • अन्यथा जब p1 mod s1 का आकार mark mod s1 के आकार के समान है, तो −

        • round := (s1 का आकार * n1 - p1) / (p1 - mark)

        • p1 := p1 + round * (p1 - mark)

        • p2 := p2 + round * (p2 - s2 का आकार)

  • p2 / s2 का आकार / n2 लौटाएं

उदाहरण 

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#include <bits/stdc++.h> using namespace std; class Solution { public:    int getMaxRepetitions(string s1, int n1, string s2, int n2) {       for (auto c : s2) {          if (s1.find(c) == string::npos)             return 0;       }       int p1 = 0, p2 = 0, mark = 0;       while (p1 < s1.length() * n1) {          char c = s2[p2 % s2.length()];          while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)          p1++;          p2++;          p1++;          if (p2 % s2.length() == 0) {             if (p2 == s2.length()) {                mark = p1;             }             else if (p1 % s1.length() == mark % s1.length()) {                int round = (s1.length() * n1 - p1) / (p1 - mark);                p1 += round * (p1 - mark);                p2 += round * (p2 - s2.length());             }          }       }       return p2 / s2.length() / n2;    } }; main() {    Solution ob;    cout << (ob.getMaxRepetitions("acb",4,"ab",2)); }

इनपुट

"acb",4,"ab",2

आउटपुट

2

  1. C++ में The Maze II C++ में The Maze II

    मान लीजिए एक भूलभुलैया में खाली स्थान और दीवारों के साथ एक गेंद है। अब गेंद किसी भी दिशा जैसे ऊपर, नीचे, बाएँ या दाएँ खाली पथों से गुजर सकती है, लेकिन यह तब तक लुढ़कना बंद नहीं करेगी जब तक यह दीवार से नहीं टकराती। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्थिति, गंतव्य

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. N कट के बाद वृत्त के टुकड़ों की संख्या गिनें C++ में N कट के बाद वृत्त के टुकड़ों की संख्या गिनें C++ में

    हमें एक पूर्णांक N दिया गया है जो 2D-वृत्त पर लगाए गए कट की संख्या को दर्शाता है। प्रत्येक कट वृत्त को दो हिस्सों में विभाजित करता है। लक्ष्य N कट के बाद वृत्त के टुकड़ों को ढूंढना है। टुकड़ों की संख्या = 2 * कट की संख्या उदाहरण से समझते हैं इनपुट - N=1 आउटपुट - वृत्त के टुकड़े: 2 व्याख्या इनपुट -