904. Repeat Until Found
A tile printer stamps the strip a over and over, edge to edge, to produce a longer and longer ribbon. A customer brings a sample strip b and wants to know when it first becomes visible somewhere inside the ribbon.
Return the smallest number of stampings of a (copies joined end to end) such that b occurs as a contiguous piece of the joined text. If this never happens, return -1. The piece may start in the middle of a copy and may cross copy boundaries.
Aim for time O(n + m), where n and m are the lengths of a and b, and O(m) extra space.
Example 1
- Input:
- a = "tide", b = "detidetidet"
- Output:
- 4
- Explanation:
Four copies give 'tidetidetidetide', and 'detidetidet' starts at index 3 and ends at index 13, so 4 copies are needed (3 copies only have 12 letters).
Example 2
- Input:
- a = "ping", b = "pingpingpingping"
- Output:
- 4
- Explanation:
Four copies glued together are exactly the second string.
Example 3
- Input:
- a = "abca", b = "cb"
- Output:
- -1
- Explanation:
No copy-joined text contains 'cb', so the answer is -1.
Constraints
1 ≤ a.length, b.length ≤ 105
Both strings contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n+m)
- Space
- O(m)