C++ में दोहराव की गणना करें

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

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

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

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

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

होगा

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

s2 में प्रत्येक वर्ण c के लिए
- यदि c, s1 में नहीं है, तो -
  - वापसी 0
p1 :=0, p2 :=0, निशान :=0
जबकि p1
- c :=s2[p2 mod size of s2]
- जबकि (s1[p1 mod size of s1] c के बराबर नहीं है और p1
  - (p1 को 1 से बढ़ाएं)
- (p2 को 1 से बढ़ाएं)
- (p1 को 1 से बढ़ाएं)
- यदि s2 का p2 मॉड आकार 0 के समान है, तो -
  - यदि p2 s2 के आकार के समान है, तो -
    - निशान :=p1
  - अन्यथा जब s1 का p1 मॉड आकार s1 के मॉड आकार के निशान के समान होता है, तो -
    - गोल :=(s1 * n1 - p1 का आकार) / (p1 - चिह्न)
    - p1 :=p1 + राउंड * (p1 - मार्क)
    - p2 :=p2 + गोल * (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