An related but slightly easier problem to the original one is finding the maximal # of `s2`

that can be obtained from `S1`

.

For example, assume `n2 = 3`

and we can get 7 `s2`

from `S1`

, the final answer will be `7/3 = 2`

I start w/ a brute force algorithm by having two pointer `p1`

and `p2`

, which iterate through `S1`

and `S2`

respectively. This part is pretty straightforward.

The brute force algorithm has some room to improve when the `n1`

is large. After some iterations, we may have enough information to calculate the answer w/o continuing.

For example, assume the following input

- s1 = "aaaaaab"
- n1 = 1,000,000
- s2 = "bc"

After the second iteration, we know we won't be able to find a match.

For those cases in which there are an answer, it's very like that there will be recurring pattern.

For example, assume the following input

- s1 = "ababc"
- n1 = 1,000,000
- s2 = "ba"

```
def get_max_repetitions(s1, n1, s2, n2)
count = get_max_repetitions_helper(s1, n1, s2)
count / n2
end
def get_max_repetitions_helper(s1, n1, s2)
p2 = 0
positions = []
(0...s1.size*n1).each do |p1|
# Give up when no char when can be matched w/ a full cyle
cycle = p1 / s1.size
return 0 if positions.size < cycle
c1, c2 = s1[p1 % s1.size], s2[p2 % s2.size]
if c1 == c2
positions[p2] = p1
# puts positions.each_with_index.map { |k,i| "(#{i}, #{k})" }.join(", ")
(p2-s2.size).step(0, -s2.size) do |i|
# Found pair (i, positions[i]) and (p2, positions[p2])
# where (p2-i) % s2.size == 0 and
# (positions[p2] - positions[i]) % s1.size == 0
if (p1 - positions[i]) % s1.size == 0
parts = [
(positions.size-1),
(s1.size*n1-p1) / (positions[p2] - positions[i]) * (p2-i),
# How many extra s2 char can we match if
# if move p1 from [positions[i], positions[i+remain])
positions[i..-1].select do |k|
# [ -------- remaining step for s1 ----------- ]
k <= (s1.size*n1-p1) % (positions[p2] - positions[i]) + positions[i] - 1
end.size
]
num_of_chars = parts.reduce(&:+)
return num_of_chars / s2.size
end
i -= s2.size
end
p2 += 1
end
end
positions.size / s2.size
end
```