สมมติว่าเรามีสตริงไม่ว่างสองสตริง s1 และ s2 (สูงสุด 100 ตัวอักษร) และตัวเลขสองตัว n1 และ n2 อยู่ในช่วง 0 ถึง 10^6 สมมติว่าสตริง S1 และ S2 โดยที่ S1=[s1,n1] และ S2=[s2,n2]
S = [s,n] 定 nghĩa สตริง 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
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- ตรวจสอบทุกตัวอักษร c ใน s2: ถ้า c ไม่อยู่ใน s1 คืนค่า 0
- p1 := 0, p2 := 0, mark := 0
- while p1 < len(s1)*n1: c := s2[p2 % len(s2)]; while s1[p1 % len(s1)] != c และ p1 < len(s1)*n1: p1++; p2++; p1++;
- ถ้า p2 % len(s2) == 0: ถ้า p2 == len(s2) mark := p1; else if p1 % len(s1) == mark % len(s1): round := (len(s1)*n1 - p1) / (p1 - mark); p1 += round * (p1 - mark); p2 += round * (p2 - len(s2))
- คืนค่า p2 / len(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
