मान लीजिए हमारे पास दो गैर-खाली स्ट्रिंग्स 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