Участник:Turk0v/Count The Repetitions

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        n = min(len(s2) + 1, n1)
        res = [0] * (n + 1)
        id = [0] * (n + 1)
        tmp_least = [-1] * len(s2)
        tmp_least[0] = 0
        j = 0
        count = 0
        for k in range(1, n + 1):
            for i in range(len(s1)):
                if s1[i] == s2[j]:
                    j += 1
                    if j == len(s2):
                        count += 1
                        j = 0
            res[k] = count
            id[k] = j
            if tmp_least[j] >= 0:
                start = tmp_least[j]
                interval = k - start
                repeat, remain = divmod(n1 - start, interval)
                pat = (res[k] - res[start]) * repeat
                rem = res[start + remain]
                return int((pat + rem) / n2)
            tmp_least[j] = k
        return int(res[n1] / n2)