1811. How Many Copies Before It Fits Inside

Print the smallest number of copies k >= 1 such that b appears somewhere inside a written out k times in a row. Print -1 if no number of copies ever contains b.

a = abcd, b = cdabcdab -> 3 abcdabcdabcd contains it, abcdabcd does not a = abc, b = bca -> 2 it straddles the seam a = abc, b = abc -> 1 a = abc, b = cba -> -1 a = aa, b = aaaaa -> 3

Check the first one. Two copies give abcdabcd, eight characters, and b has eight characters but starts at c, so it would have to begin at position 2 and run to position 9. Three copies give the twelve characters it needs.

## What most people try first

Build one copy, search, build two, search again, and so on. Each search costs the length of the text so far, so the total is 1 + 2 + ... + k copies of a, which is O(k^2 |a|). With |b| = 200000 and |a| = 2 that is k = 100000 and about 10^10 characters examined. The method below builds ONE string and runs one search: about 1.6 * 10^6 steps.

## Two copies more than you think you need is always enough

Let n = |a| and m = |b|. If b occurs at all, it occurs inside a repeated ceil(m / n) + 1 times.

Why: any occurrence starts at some position pos. Because the repeated string has period n, an occurrence starting at pos >= n also occurs at pos - n. So there is an occurrence with pos < n, and it ends before n + m, which is inside ceil(m/n) + 1 copies since that has length at least m + n.

So build big = a repeated ceil(m/n) + 1 times, search b in it with the prefix function of problem 1802, and take the FIRST match:

pos = first occurrence of b in big, or -1 if pos < 0: print -1 else: print max(1, ceil((pos + m) / n))

The answer is how many copies the match reaches into, which is ceil((pos + m) / n), with the floor of 1 for the case where b is empty of demands and fits in the first copy.

## Why the first match gives the smallest k

Copies are added on the right, so the set of positions available grows with k. A match that ends earlier needs no more copies than one that ends later, and the first match in left-to-right order is the one that ends earliest among those that start earliest. Taking the earliest start gives the earliest possible end, because the length is fixed.

## Cost

O(m + n) for building and O(m + n) for the search, so about 1.6 * 10^6 steps at the limits. Memory is O(m + n): big is at most m + 2n characters, which is 600000 at the limits.

Constraints - `1 ≤ length of a ≤ 200000` - `1 ≤ length of b ≤ 200000` - both strings contain only lowercase English letters - the answer, when it exists, never exceeds `ceil(|b| / |a|) + 1` - only whether `b` occurs at all matters, so overlapping occurrences make no difference, and a number of copies is wanted rather than a position