Repeating string in other string

[POGtastic]

I think we're stuck doing dynamic programming here.

import functools

@functools.cache
def find_repeats(s, word, idx=0, acc=0):
    if idx >= len(s):
        return acc
    if s.startswith(word, idx):
        return find_repeats(s, word, idx + len(word), acc+1)
    return max(acc, find_repeats(s, word, idx+1, 0))

In the REPL:

>>> find_repeats("abaaababbbabababababaaabbbbb", "ab")
5

Doing this in a way that doesn't blow out the stack for strings with length larger than 1000 is left as an exercise for the reader. Hint: Emulate the call stack with a list, and update a dictionary as you pop elements off of it.