On this page
Description
How many copies of "wxyz" does it take to contain "yzwxyzwx"? Is "erwat" a rotation of "water"? Is "xyzxyzxyz" just "xyz" repeated? These are questions about periodic strings. The trick in each is knowing how much repetition can possibly matter, so the search stays bounded and short. This skill covers the copy bound, the doubling trick, and the period that the KMP failure function gives you for free.
We'll go from simple to more technical:
- The pattern: repeat until long enough, then at most one more copy.
- A second flavor: look inside s + s for rotations and repeated blocks.
- Where periodicity shows up in production (rotations, circular IDs, ring buffers).
- What breaks it: no bound, one copy too few, missing length checks, untrimmed doubling.
The approach
Java
int repeatedStringMatch(String a, String b) {
int q = (b.length() + a.length() - 1) / a.length(); // ceil(|b| / |a|): the fewest copies long enough
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) sb.append(a);
if (sb.indexOf(b) >= 0) return q;
if (sb.append(a).indexOf(b) >= 0) return q + 1; // b may straddle into one more copy
return -1;
}
Python
def repeated_string_match(a: str, b: str) -> int:
q = -(-len(b) // len(a)) # ceil(|b| / |a|): the fewest copies long enough
if b in a * q:
return q
if b in a * (q + 1): # b may straddle into one more copy
return q + 1
return -1
Fewer than q copies are too short to hold b. More than q + 1 never helps: any occurrence of b can be shifted back by whole copies of a until it starts inside the first copy, at an offset below |a|, so it ends before |a| + |b|, which is at most (q + 1) copies. If q + 1 copies don't contain b, no number of copies does. "abc" and "cabcabca" show why the extra copy matters: 3 copies miss it, 4 contain it.
A second flavor: look inside s + s
Doubling a string lays out every rotation of it side by side:
Java
boolean isRotation(String a, String b) {
return a.length() == b.length() && (a + a).contains(b);
}
boolean repeatedSubstringPattern(String s) { // two or more copies of one block?
String doubled = s + s;
return doubled.substring(1, doubled.length() - 1).contains(s);
}
Python
def is_rotation(a: str, b: str) -> bool:
return len(a) == len(b) and b in a + a
def repeated_substring_pattern(s: str) -> bool: # two or more copies of one block?
return s in (s + s)[1:-1]
Every rotation of a appears in a + a - but so does every shorter substring, so the length check is essential: without it, "a" counts as a rotation of "ab". For repeated blocks, s always occurs in s + s at positions 0 and n; removing the first and last characters rules those out, and s still occurs elsewhere exactly when shifting it by some period gives s again - that is, when s is made of a repeated block.
Where you'll see it
Detecting a repeating unit in logs or sensor readings, comparing circular identifiers (the same cycle starting at a different point), and finding tandem repeats in DNA all use periodicity. Circular buffers and ring-shaped data are routinely "unrolled" by doubling so a wrapping sequence becomes an ordinary substring.
Which tool for which job?
| You need | Use |
|---|---|
| Fewest copies of a containing b | copies until the length is ≥ len(b), then try one more |
| Is b a rotation of a? | equal lengths and b in a + a |
| Is s a repeated block? | s in (s + s)[1:-1], or the KMP period test |
| The smallest period | p = n - lps[n - 1] |
| A canonical form for rotation-equivalent strings | the least rotation (Booth's algorithm) |
| Guaranteed linear search in Java | KMP or Z, not indexOf |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No upper bound on copies | never ends when b can't occur | at most ceil(len(b) / len(a)) + 1 copies |
| Stopping at q copies | misses matches that straddle copies | try q + 1 |
| Rotation without a length check | "a" counts as a rotation of "ab" | compare lengths first |
| Untrimmed doubling | everything looks repeated | search (s + s)[1:-1] |
Trusting Java's indexOf to be linear | O(n × m) worst case | KMP for adversarial input |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why are ceil(|b| / |a|) + 1 copies of a always enough to decide whether b fits?
Show answer
Any occurrence of b in repeated copies of a can be shifted back by whole copies until it starts inside the first copy, at an offset below |a|. It then ends before |a| + |b| characters, which fit in ceil(|b| / |a|) + 1 copies. If that many copies don't contain b, no number of copies does.
2. Why does a rotation check need a.length() == b.length() as well as (a + a).contains(b)?
Show answer
a + a contains every rotation of a - but also every substring of those rotations. Without the length check, "a" would count as a rotation of "ab".
3. Why does the repeated-block check remove the first and last characters of s + s?
Show answer
s occurs in s + s at positions 0 and n for every string. Trimming one character from each end destroys those two occurrences; s can still be found only at a shift that is a period of s, which happens exactly when s is two or more copies of a block.
Key takeaways
- b fits in copies of a within ceil(|b| / |a|) or one more copy - never more.
- Rotations of a all live in a + a; compare lengths too.
- s is a repeated block exactly when it occurs in (s + s) minus its first and last characters.
- Bound every "repeat until" loop.
indexOfis naive: O(n * m) worst case; KMP makes it linear.