C++, 3ms, find reoccurence and skip
Every time we find a complete s2 in n1\s1, we record three things using a map:\n key: current position in s1\n value: current position in n\s1 and how many s2 h
Every time we find a complete s2 in n1\\*s1, we record three things using a map:\n* key: current position in s1\n* value: current position in n\\*s1 and how many s2 have been found.\n\nLater, we check if current position in s1 has been recorded before, and if so, we can skip reoccurrence of all s1[i0:i](see what i0 and i mean in code below) in n1\\*s1.\n\n```\nclass Solution {\npublic:\n    int getMaxRepetitions(string s1, int n1, string s2, int n2) {\n        unordered_map<int, pair<int, int>> r;\n        \n        int k = 0;\n        for(int i = 0; i < s1.length()*n1;) {\n            \n            int rr = i % s1.length();\n            if(r.find(rr) == r.end()) {\n                r[rr] = make_pair(i, k);\n                // cout << "setup: " << rr << ',' << i << ',' << k << endl;\n            }\n            else {\n                // cout << rr << ',' << i << ',' << k << endl;\n                auto i0 = r[rr].first;\n                auto k0 = r[rr].second; // now, i - i0 == (k - k0) * s2.length()\n                \n                int n = (s1.length()*n1 - i0) / (i - i0); // we have n*(k - k0) complete s2 left\n                \n                // skip repeated patterns\n                i = i0 + n*(i - i0);\n                k = k0 + n*(k - k0);\n            }\n            \n            for(int j = 0; i < s1.length()*n1 && j < s2.length(); ++ i, ++ j) {\n                while(i < s1.length()*n1 && s1[i%s1.length()] != s2[j]) ++ i;\n            }\n            \n            if(i >= s1.length()*n1) {\n                break;\n            }\n            \n            ++ k;\n        }\n        \n        // cout << k << endl;\n        return k / n2;\n    }\n    \n    inline string repeat(string &s, int n) {\n        string S;\n        S.reserve(s.size()*n);\n        while(n -- > 0) {\n            S += s;\n        }\n        return S;\n    }\n};\n\n```
[]