C++ 0ms O(str1.length*str2.length)
IDEA: \n\nGiven 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
IDEA: \n\n**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].**\nIn 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)).\n\ndefine a division and a modulo between two strings as follow: \n\nstr/str2=argmax{i, (str2,i) can be obtained by str}\nstr%str2=the v mentioned above associated with str.\n\nAll possible values of v is less than str2.size(), \nso (str1,n)%str2 will begin to **repeat a pattern** after a certain n less than str2.size(). \n(the pattern is the same because in the cases with the same v, our situations are exactly the same), \nso is (str1,n)/str2-(str1,n+1)/str2 for the same reason. \nWe can therefore precompute a table for all these values with O(str1.length*str2.length).\n\n(str1,n) can be divided in three parts:\n\nsth before pattern(A)    +    pattern parts(B)    +    sth after pattern(C)\n\nThe pattern does not necessarily begin in the first str1, we shall see if n is great enough so that there can be a pattern.\n\nThe last pattern(C) is not necessarily complete, we need to calculate it separately.\n\nWe can finish in just looking to the precomputed table and doing some simple maths. \n\n\n```\nclass Solution {\npublic:\n    int getMaxRepetitions(string s1, int n1, string s2, int n2) {\n        vector<int> rapport(102,-1);\n        vector<int> rest(102,-1);\n        int b=-1;int posRest=0;int rap=0;\n        int last=-1;\n        rapport[0]=rest[0]=0;//case when n=0\n        for(int i=1;i<=s2.size()+1;i++){\n            int j;\n            for(j=0;j<s1.size();j++){\n                if(s2[posRest]==s1[j]){\n                    posRest++;\n                    if(posRest==s2.size()){\n                        rap++;\n                        posRest=0;\n                    }\n                }\n            }\n            for(int k=0;k<i;k++){\n                if(posRest==rest[k]){b=k;last=i;break;}\n            }\n            rapport[i]=rap;rest[i]=posRest;\n            if(b>=0)break;\n        }\n        int interval=last-b;\n        if(b>=n1)return rapport[n1]/n2;\n        return ((n1-b)/interval*(rapport[last]-rapport[b])+rapport[(n1-b)%interval+b])/n2;\n//corrected thanks to @zhiqing_xiao and @iaming \n    }\n};\n```
[]