0465MediumStringString MatchingZ AlgorithmKnuth–Morris–Pratt AlgorithmBoyer–Moore String-Search Algorithm

Repeats Of A Motif Holding A Stretch

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A loom weaves a band by repeating the pattern motif end to end, so weaving it three times gives a band reading motif then motif then motif with nothing between them. Each letter stands for one pick of the shuttle.

A buyer wants the band to contain stretch as an unbroken run of picks somewhere along it, anywhere at all - the run need not start where a copy of the motif starts.

Return the smallest number of whole repeats of motif that produces a band containing stretch. Return -1 if no number of repeats ever does. Only whole repeats count: the loom cannot stop part way through the motif, though the wanted run may finish before the band does.

Examples

Example 1

Input: motif = "ptr", stretch = "rptrp"
Output: 3

Weaving the motif three times gives ptrptrptr, and the wanted run sits in it starting at the third pick.

Example 2

Input: motif = "gh", stretch = "hg"
Output: 2

One repeat reads gh, which does not hold hg, while two repeats read ghgh and hold it across the join.

Example 3

Input: motif = "mno", stretch = "nomx"
Output: -1

Every band woven from mno is made only of m, n and o picks, so a run containing x can never appear.

Constraints

1 <= motif.length <= 10^4
1 <= stretch.length <= 10^4
motif and stretch consist of lowercase English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def motif_repeats(motif: str, stretch: str) -> int:

Java

public int motifRepeats(String motif, String stretch)

The intended approach

Time O(a + b) for a motif of a letters and a stretch of b letters, the woven band being O(a + b) long.Space O(a + b) for the woven band and the prefix table.

A run of the wanted stretch needs enough repeats to cover its own length, and at most one repeat more because the run may begin part way through a copy; beyond that a further repeat adds nothing new. So weave that many copies, scan them for the earliest occurrence with a prefix-function match that never backs up over the band, and count how many repeats the end of that occurrence reaches into. No occurrence in the woven band means no band ever holds it.

Pythonentry point: motif_repeats

def motif_repeats(motif, stretch):
    # Any run of the required stretch sits inside enough copies to cover its
    # length, plus at most one more to allow for starting part way through a
    # copy. Weave that many copies and find the earliest run with a
    # prefix-function scan, then count the copies that run reaches into.
    # O(len(motif) + len(stretch)) time and space.
    span = len(motif)
    need = len(stretch)
    copies = -(-need // span) + 1
    band = motif * copies
    fail = [0] * need
    k = 0
    for i in range(1, need):
        while k and stretch[i] != stretch[k]:
            k = fail[k - 1]
        if stretch[i] == stretch[k]:
            k += 1
            fail[i] = k
        else:
            fail[i] = 0
    j = 0
    for i in range(len(band)):
        while j and band[i] != stretch[j]:
            j = fail[j - 1]
        if band[i] == stretch[j]:
            j += 1
            if j == need:
                start = i - need + 1
                return -(-(start + need) // span)
    return -1

The obvious version

Weave one more copy at a time, searching the whole band for the stretch after each, and stop at the first count that holds it, giving up once the band is far longer than any run could need. O(b) searches over a band that keeps growing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_motif_repeats(motif, stretch):
    limit = len(stretch) + 2
    band = ""
    for count in range(1, limit + 1):
        band += motif
        if stretch in band:
            return count
    return -1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in