Find the cycle. Python, fast with explanation
This is a difficult problem (for me anyway). I kept thinking that there had to be a trick\n\nFirstly, if there is any character in s2 that is not in s1 then we 
This is a difficult problem (for me anyway). I kept thinking that there had to be a trick\n\nFirstly, if there is any character in `s2` that is not in `s1` then we can never obtain `[S2, M]` from `S1`.\n\nThen I step through `s1`, incrementing an index pointer in `s2` whenever characters match :\n* When I reach the end of `s2`, go back to the start and increment the counter `s2_reps` that tells me how many complete copies of `s2` I have used.\n* Similarly when I reach the end of `s1`, go back to the start and increment `s1_reps`.\n* At then end of `s1` record in a dictionary a mapping from the next index to be matched in `s2` as key and the pair of `(s1_reps, s2_reps)` as value.\n* If the key has been seen before then we are in a loop, every time we go through `s1` we are at the same position in `s2`. So we can break from stepping through the strings and work out how many loops we can go through for all of `[s1, n1]`.\n\n(Potentially we never find a loop and have reached `n1` repetitions of `s1` already so can just return `s2_reps // n2`)\n\nHaving found how many repetitions of `s1` and `s2` there are in a loop, we use as many loops as possible to go through `n1` copies of `s1`. Bear in mind that there may be some repetitions before the loop is entered.\nThen all that remains is if we have not seen `n1` copies of `s1` after the final loop, step through the strings again until we reach `n1`.\n\nI suspect the code below could be made a little more efficient. Comments welcome! \n```\nclass Solution(object):\n    def getMaxRepetitions(self, s1, n1, s2, n2):\n\n        if any(c for c in set(s2) if c not in set(s1)):   # early return if impossible\n            return 0\n\n        s2_index_to_reps = {0 : (0, 0)}   # mapping from index in s2 to numbers of repetitions of s1 and s2\n        i, j = 0, 0\n        s1_reps, s2_reps = 0, 0\n\n        while s1_reps < n1:\n\n            if s1[i] == s2[j]:\n                j += 1     # move s2 pointer if chars match\n            i += 1\n\n            if j == len(s2):\n                j = 0\n                s2_reps += 1\n\n            if i == len(s1):\n                i = 0\n                s1_reps += 1\n                if j in s2_index_to_reps:   # loop found, same index in s2 as seen before\n                    break\n                s2_index_to_reps[j] = (s1_reps, s2_reps)\n\n        if s1_reps == n1:    # already used n1 copies of s1\n            return s2_reps // n2\n\n        initial_s1_reps, initial_s2_reps = s2_index_to_reps[j]    # repetitions before loop starts\n        loop_s1_reps = s1_reps - initial_s1_reps\n        loop_s2_reps = s2_reps - initial_s2_reps\n        loops = (n1 - initial_s1_reps) // loop_s1_reps\n\n        s2_reps = initial_s2_reps + loops * loop_s2_reps\n        s1_reps = initial_s1_reps + loops * loop_s1_reps\n\n        while s1_reps < n1:   # if loop does not end with n1 copies of s1, keep going\n\n            if s1[i] == s2[j]:\n                j += 1\n            i += 1\n\n            if i == len(s1):\n                i = 0\n                s1_reps += 1\n\n            if j == len(s2):\n                j = 0\n                s2_reps += 1\n\n        return s2_reps // n2\n```
['Python']