class Solution(object):
    
    def getMaxRepetitions(self, s1, n1, s2, n2):
        #http://www.cnblogs.com/grandyang/p/6149294.html
        #memoization: use dictionary to find loop where x*s1 contains y*s2, and each loop start with the same index of s2 
        #key=next_index, val=(s1_rep,s2_rep)
        #each item indicates, for s1_rep reps of s1, there are maximum s2_rep reps of s2 and the next_index of s2 to search for is next_index
        rep_count={} 
        s1_rep,s2_rep,next_index=0,0,0
        
        while s1_rep<n1:
            print rep_count
            s1_rep+=1
            for ch in s1:
                if ch==s2[next_index]:
                    next_index+=1
                    if next_index==len(s2):
                        next_index=0
                        s2_rep+=1
            print next_index,s1_rep,s2_rep
            if next_index in rep_count:
                #found loop 
                prev_s1_rep,prev_s2_rep=rep_count[next_index]
                interval=s1_rep-prev_s1_rep #length of loop
                repeats=(n1-prev_s1_rep)/interval #number of loops 
                res=repeats*(s2_rep-prev_s2_rep) #first find the number of s2 in all the loops 
                remain_s1_rep=(n1-prev_s1_rep)%interval+prev_s1_rep #number of repetitions not in the loops 
                for key,val in rep_count.iteritems():
                    if val[0]==remain_s1_rep:
                        res+=val[1]
                        break
                return res/n2
            
            else: 
                rep_count[next_index]=(s1_rep,s2_rep)
        return s2_rep/n2