비어 있지 않은 두 개의 문자열 s1과 s2(최대 100자)가 있고 두 개의 숫자 n1과 n2가 모두 0에서 106 사이의 범위에 있다고 가정합니다. 이제 S1=[s1,n1] 및 S2=[인 문자열 S1과 S2를 가정합니다. s2,n2].
S =[s,n]은 n개의 연결된 문자열 s로 구성된 문자열 S를 정의합니다. 예를 들면 ["ab", 4] ="abababab"입니다.
반면에 s1이 되도록 s2에서 일부 문자를 제거하면 문자열 s1을 문자열 s2에서 얻을 수 있다고 정의합니다. 따라서 "abc"는 정의에 따라 "abdbec"에서 얻을 수 있지만 "acbbe"에서는 얻을 수 없습니다.
S1에서 [S2,M]을 얻을 수 있도록 최대 정수 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 size of s1]은 c와 같지 않고 p1
-
(p1을 1씩 증가)
-
-
(p2를 1씩 증가)
-
(p1을 1씩 증가)
-
s2의 p2 mod 크기가 0과 같으면 -
-
p2가 s2의 크기와 같으면 -
-
마크 :=p1
-
-
그렇지 않으면 s1의 p1 모드 크기가 s1의 표시 모드 크기와 같으면 -
-
round :=(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