IDEA:

**Given a str2, for each str, we can give a value v to this str such that, after greedily looking through str, our imaginary next step is to find str2[v].**

In our problem, str is always (str1,n), with a given str1, so, we can take one more step and say that for each n, there is a unique v associated to n(i.e t0 (str,n)).

define a division and a modulo between two strings as follow:

str/str2=argmax{i, (str2,i) can be obtained by str}

str%str2=the v mentioned above associated with str.

All possible values of v is less than str2.size(),

so (str1,n)%str2 will begin to **repeat a pattern** after a certain n less than str2.size().

(the pattern is the same because in the cases with the same v, our situations are exactly the same),

so is (str1,n)/str2-(str1,n+1)/str2 for the same reason.

We can therefore precompute a table for all these values with O(str1.length*str2.length).

(str1,n) can be divided in three parts:

sth before pattern(A) + pattern parts(B) + sth after pattern(C)

The pattern does not necessarily begin in the first str1, we shall see if n is great enough so that there can be a pattern.

The last pattern(C) is not necessarily complete, we need to calculate it separately.

We can finish in just looking to the precomputed table and doing some simple maths.

```
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
vector<int> rapport(102,-1);
vector<int> rest(102,-1);
int b=-1;int posRest=0;int rap=0;
int last=-1;
rapport[0]=rest[0]=0;//case when n=0
for(int i=1;i<=s2.size()+1;i++){
int j;
for(j=0;j<s1.size();j++){
if(s2[posRest]==s1[j]){
posRest++;
if(posRest==s2.size()){
rap++;
posRest=0;
}
}
}
for(int k=0;k<i;k++){
if(posRest==rest[k]){b=k;last=i;break;}
}
rapport[i]=rap;rest[i]=posRest;
if(b>=0)break;
}
int interval=last-b;
if(b>=n1)return rapport[n1]/n2;
return ((n1-b)/interval*(rapport[last]-rapport[b])+rapport[(n1-b)%interval+b])/n2;
//corrected thanks to @zhiqing_xiao and @iaming
}
};
```