8.22 - hard - 89

466. Count The Repetitions
这题好困难，看了答案也很难理解，估计只能背答案了。。。等复习的时候再来做一次。

class Solution(object):
     def getMaxRepetitions(self, s1, n1, s2, n2):

        if any(c for c in set(s2) if c not in set(s1)):   # early return if impossible
            return 0

        s2_index_to_reps = {0 : (0, 0)}   # mapping from index in s2 to numbers of repetitions of s1 and s2
        i, j = 0, 0
        s1_reps, s2_reps = 0, 0

        while s1_reps < n1:

            if s1[i] == s2[j]:
                j += 1     # move s2 pointer if chars match
            i += 1

            if j == len(s2):
                j = 0
                s2_reps += 1

            if i == len(s1):
                i = 0
                s1_reps += 1
                if j in s2_index_to_reps:   # loop found, same index in s2 as seen before
                    break
                s2_index_to_reps[j] = (s1_reps, s2_reps)

        if s1_reps == n1:    # already used n1 copies of s1
            return s2_reps // n2
        # 完整的x个s1可以循环到y个s2，最后结束的地方是s2[j]
        initial_s1_reps, initial_s2_reps = s2_index_to_reps[j]    # repetitions before loop starts
        loop_s1_reps = s1_reps - initial_s1_reps # 计算每一个整loop，需要多少个s1
        loop_s2_reps = s2_reps - initial_s2_reps
        loops = (n1 - initial_s1_reps) // loop_s1_reps

        s2_reps = initial_s2_reps + loops * loop_s2_reps
        s1_reps = initial_s1_reps + loops * loop_s1_reps

        while s1_reps < n1:   # if loop does not end with n1 copies of s1, keep going

            if s1[i] == s2[j]:
                j += 1
            i += 1

            if i == len(s1):
                i = 0
                s1_reps += 1

            if j == len(s2):
                j = 0
                s2_reps += 1

        return s2_reps // n2