class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int m = chs1.length;
        int n = chs2.length;
        long[][] dp = new long[m][31];
        // dp[i][k] means the length of s1 required to match 2^k s2,
        // from the ith char of s1.
        // dp[i][k] = dp[i][k - 1] + dp[(i + dp[i][k - 1]) % m][k - 1]
        for (int i = 0; i < m; i++) {
            int l1 = i, l2 = 0;
            for (; l2 < n; l1++, l2++)
                for (; l1 < m * n1 && chs1[l1 % m] != chs2[l2]; l1++);
            dp[i][0] = l1 - i;
        }
        boolean loop = true;
        for (int k = 1; loop && k < 31; k++) {
            for (int i = 0; i < m; i++) {
                long prev = dp[i][k - 1];
                dp[i][k] = prev + dp[(int) ((i + prev) % m)][k - 1];
            }
        }
        long res = 0L, i = 0L;
        for (int k = 30; 0 <= k; k--) {
            long next;
            while ((next = i + dp[(int) (i % m)][k]) <= m * n1) {
                res += 1 << k;
                i = next;
            }
        }
        return (int) (res / n2);
    }
}