ধরি আমাদের দুটি খালি নন-স্ট্রিং s1 এবং s2 (সর্বোচ্চ 100 ক্যারেক্টার) এবং দুটি সংখ্যা n1 এবং n2 আছে (0 থেকে 10^6 পর্যন্ত)। এখন ধরি S1 এবং S2, যেখানে S1 = [s1, n1] এবং S2 = [s2, n2]।
S = [s, n] মানে স্ট্রিং S যা s স্ট্রিংটি n বার সংযুক্ত করে তৈরি। উদাহরণ: ["ab", 4] = "abababab"।
দूसरी পাশে, স্ট্রিং s1 কে s2 থেকে কিছু ক্যারেক্টার বাদ দিয়ে পাওয়া যাবে। যেমন "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.length() * n1:
- c := s2[p2 % s2.length()]
- যখন (s1[p1 % s1.length()] != c এবং p1 < s1.length() * n1): p1++
- p2++; p1++
- যদি p2 % s2.length() == 0:
- যদি p2 == s2.length(): mark := p1
- অন্যথায় যদি p1 % s1.length() == mark % s1.length():
- round := (s1.length() * n1 - p1) / (p1 - mark)
- p1 := p1 + round * (p1 - mark)
- p2 := p2 + round * (p2 - s2.length())
- ফেরত: p2 / s2.length() / 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;
}
};
int main() {
Solution ob;
cout << (ob.getMaxRepetitions("acb", 4, "ab", 2));
}
ইনপুট
"acb", 4, "ab", 2
আউটপুট
2
