Repeated String Match

Two candidate repetitions, and a reason there is never a third

time O(n * m)space O(n + m)

The trap here is not knowing when to stop repeating. Two facts pin it down. The repetition must be at least as long as b, which sets the floor at ceil(len(b) / len(a)) copies. And one extra copy on top of that is always enough: any occurrence of b can be shifted left by whole copies until it starts inside the very first copy, and from there it can run no further than one copy past the floor. So exactly two candidates need testing — the floor and the floor plus one. If neither works, no number ever will, and the search is over after two scans instead of an infinite loop.

Details

Animated on: a = "abcd", b = "cdabcdab" — repeat a the fewest times so that b is a substring of the result, or return -1 if that is impossible.

Problem:Repeated String MatchMedium

Two candidate repetitions, and a reason there is never a third

step 1 / 9

[0]

[1]

[2]

[3]

a = "abcd" is 4 characters and b = "cdabcdab" is 8. A string can never contain something longer than itself, so 2 copies (8 characters) is the smallest repetition worth testing at all.

Pseudocode

1FUNCTION repeatedStringMatch(a, b):
2  k <- CEIL(LENGTH(b) / LENGTH(a))
3  FOR copies <- k TO k + 1:
4    s <- REPEAT(a, copies)
5    FOR i <- 0 TO LENGTH(s) - LENGTH(b):
6      m <- 0
7      WHILE m < LENGTH(b) AND s[i + m] = b[m]:
8        m <- m + 1
9      IF m = LENGTH(b):
10        RETURN copies
11  RETURN -1

← / → step · space play · Home restart

Every step in words

Show all 9 steps

a = "abcd" is 4 characters and b = "cdabcdab" is 8. A string can never contain something longer than itself, so 2 copies (8 characters) is the smallest repetition worth testing at all.
2 copies of "abcd" gives 8 characters — just enough room for b's 8. That leaves 1 start position to try, index 0.
Start 0: s[0]='a' is already not b[0]='c', so this alignment dies on its first comparison — slide right.
The only start position 2 copies allow failed. b is not ruled out yet though: it may need to straddle a copy boundary, and at 2 copies the string runs out of characters before such a start can even be tried.
One more copy appends "abcd" at cells 8..11, taking the string to 12. Those extra cells buy start positions 1 through 4, which is exactly the room b needs to begin late in one copy and finish inside a later one.
Start 0: s[0]='a' is already not b[0]='c', so this alignment dies on its first comparison — slide right.
Start 1: s[1]='b' is already not b[0]='c', so this alignment dies on its first comparison — slide right.
Starting at 2, all 8 characters line up: cells 2..9 spell "cdabcdab". That span begins in copy 1 and ends in copy 3, which is why fewer copies could not hold it.
3 copies is the answer. There is no point testing a 4th: any match must start inside the first copy (a later start is the same pattern shifted by a whole copy), so 3 copies already cover every alignment that exists.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Repeated String Match in the editor All Strings problems Back to roadmap