LC466. Count The Repetitions
Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] =”abcabcabc”.
On the other hand, 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, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.
You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1]and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.
Example:
Input:
s1="acb", n1=4
s2="ab", n2=2
Return:
2
这题好难…我看了好几个参考才懂的, 膜拜大神。
这题通过重复n1次s1构成S1，重复n2次s2构成S2，求S1里有多少S2. 思路就是求S1里有多少s2, 再除以n2. 所以repeatCnt计算到k次s1有多少s2，nextInt计算下一个s2从哪个index开始查找，如果nextInt重复了，就证明找到了重复的pattern在S1中，这个pattern里的s2就可以计算了。最后剩下的部分单独算出来，加patterm里的s2数量，就是s2的总数。如果没有pattern，就用repeatCnt的最后一个数据除以n2即可。
public class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
int[] repeatCnt = new int[n1 + 1];
int[] nextInt = new int[n1 + 1];
int j = 0, repeat = 0;
for(int k = 1; k <= n1; k++){
for(int i = 0; i < s1.length(); i++){
if(s1.charAt(i) == s2.charAt(j)){
j++;
if(j == s2.length()){
j = 0;
repeat++;
}
}
} // for i
repeatCnt[k] = repeat;
nextInt[k] = j;
for(int start = 0; start < k; start++){
// repeat pattern found
if(nextInt[start] == j){
int interval = k - start;
int echo = (n1 - start)/interval;
int patternCnt = (repeatCnt[k] - repeatCnt[start])*echo;
int remainCnt = repeatCnt[start + (n1 - start) % interval];
return (patternCnt + remainCnt)/n2;
} // if
} // for s
} // for k
return repeatCnt[n1]/n2;
}
}
O(n1*(s1.length + n1))