ধরুন আমাদের দুটি অ-খালি স্ট্রিং আছে s1 এবং s2 (সর্বাধিক 100টি অক্ষর) এবং দুটি সংখ্যা n1 এবং n2 উভয়ই 0 থেকে 106 রেঞ্জের মধ্যে রয়েছে। এখন ধরুন S1 এবং S2 স্ট্রিং, যেখানে S1=[s1,n1] এবং S2=[ s2, n2]।
S =[s,n] স্ট্রিং S সংজ্ঞায়িত করে যা n সংযুক্ত স্ট্রিং s নিয়ে গঠিত। উদাহরণ হিসেবে, ["ab", 4] ="abababab"।
অন্যদিকে, আমরা এটাও সংজ্ঞায়িত করি যে স্ট্রিং s2 থেকে স্ট্রিং s1 পাওয়া যেতে পারে যদি আমরা s2 থেকে কিছু অক্ষর সরিয়ে ফেলি যাতে এটি s1 হয়ে যায়। সুতরাং, সংজ্ঞার উপর ভিত্তি করে "abdbec" থেকে "abc" পাওয়া যেতে পারে, কিন্তু এটি "acbbe" থেকে পাওয়া যাবে না।
আমাদের সর্বাধিক পূর্ণসংখ্যা M খুঁজে বের করতে হবে যাতে S1 থেকে [S2,M] পাওয়া যায়।
সুতরাং, যদি ইনপুট হয় s1="acb", n1=4, s2="ab", n2=2, তাহলে আউটপুট হবে 2
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
s2
-এ প্রতিটি অক্ষরের জন্য c-
যদি c s1-এ না থাকে, তাহলে −
-
রিটার্ন 0
-
-
-
p1 :=0, p2 :=0, চিহ্ন :=0
-
যখন p1
করুন -
c :=s2[s2 এর p2 মোড সাইজ]
-
যখন (s1 [p1 mod এর 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
আউটপুট
2
