We define str = [s, n] as the string str which consists of the string s concatenated n times.
For example, str == ["abc", 3] =="abcabcabc". We define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1.
For example, s1 = "abc" can be obtained from s2 = "abdbec" based on our definition by removing the bolded underlined characters. You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].
Return the maximum integer m such that str = [str2, m] can be obtained from str1.
- str1 = s1*n1
- s2nm can be obtained from str1, which means, we can delete some char in s1n1 to be s2n*m
So, still binary search m?
Let me see the std.
- If the s2 has N duplicates in str1, then str2 has N/n2 duplicates in str1.
- Because, we can match s1 in s2, but also, match s1 in s2*2. For example, if we want to match 'bac' in 'abc', we must match the ac after b in the next concact string. Therefore, we store a nextstate varaible to store next position of current match character.
e.g., s2 = bcaa
j ---------------> 1 2 3 0 1 2 3 0 1 2 3 0
str1 -------------> abacb | abacb | abacb | abacb | abacb | abacb
repeatCount -----> 0 | 1 | 1 | 2 | 2 | 3
nextIndex -------> 2 | 1 | 2 | 1 | 2 | 1
we can see at first, the next index is 2, because bc match, but we need to find the a, the index of a in s2 is 2. Therefore, the nextIndex is 2. also, we match, aab in the second s2, and we want to match a, therefore the nextIndex is 1.
We can also observe that pigenhole principle, after matching several times (nextIndex is in 0, s2.size() - 1, after iterate s2.size() +1 times of s1, we will have the duplicates). Thus, we can count one by one before finding the pattern. repeat = (n1 - end) / pattern length.
Also, to find the duplicates string in the repeat, the std use a accumlated sum. The most beautiful code
// because we will have some duplicates in the tail of the end, we just move these part to the start
int remainCnt = repeatCnt[start + (n1 - start) % interval];
We can see that, start => before the pattern, and the duplicates in the tail. (n1-start) % interval. Because it's the same pattern, we can move these part to the duplicate one directly. How genius idea!
I think in this question, the most important thing is to finding the pattern and code the pattern. We use a nextindex to code some string in the next duplicates. I guess this is reason why the problem give me s1*n1!