Brilliant idea for finding repeated pattern! Here is my Java version w/ a few comments :)

public class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int l1 = str1.length, l2 = str2.length;
int[] repCnt = new int[l2 + 1];
int[] nextIdx = new int[l2];
Arrays.fill(nextIdx, -1);
int cnt = 0, cycleStart = -1, cycleEnd = -1;
for (int i = 0, s2Idx = 0; i <= l2 && i < n1; i++) { // currently processing ith occurrence of str1
for (int j = 0; j < l1; j++) { // find the first char in str1 to match str2[s2Idx]
if (str1[j] == str2[s2Idx]) {
if (++s2Idx == l2) { // reach the end of str2, increment cnt
s2Idx = 0;
cnt++;
}
}
}
for (int k = 0; k < i; k++) {
if (nextIdx[k] == s2Idx) { // find the cycle from (str1, k) -> (str1, i)
cycleStart = k;
cycleEnd = i;
break;
}
}
if (cycleStart >= 0) {break;}
repCnt[i] = cnt;
nextIdx[i] = s2Idx;
//System.out.println("i = " + i + ", repCnt = " + cnt + ", nextIdx = " + s2Idx);
}
/*
0 ... 1 ... 2 ... ... ... cycleStart ... cycleStart+1 ... ... ... cycleEnd ............ n1 - 1
| |
| .......................|
|<- part1 ->|<- part2 ->|<- part3 ->|
*/
// if n1 is large enough, it can be divided into three parts:
// Part 1: before cycle i = [0, cycleStart)
// Part 2: in the cycle [cycleStart, cycleEnd) * ?
// Part 3: remaining..., n1 - 1]
// if n1 is too small
if (cycleStart < 0) {
return repCnt[n1] / n2;
}
int part1 = repCnt[cycleStart];
int part2 = (n1 - cycleStart - 1) / (cycleEnd - cycleStart) * (cnt - repCnt[cycleStart]);
int part3 = repCnt[(n1 - cycleStart - 1) % (cycleEnd - cycleStart) + cycleStart] - repCnt[cycleStart];
return (part1 + part2 + part3) / n2;
}
}