Show problems as
Classic problem #686MediumStringString MatchingZ AlgorithmKnuth–Morris–Pratt AlgorithmBoyer–Moore String-Search Algorithm

Repeated String Match

Real-world version: Repeats Of A Motif Holding A Stretch
Tracked in this browser only
Read Repeated String Match on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def motif_repeats(motif: str, stretch: str) -> int:
Java
public int motifRepeats(String motif, String stretch)

More on the same topics