A 15ms Java Solution with explanation (brute force + memorization)
I was enlightened by the @shawngao's brute force solution, the post can be found here.\n\nThe basic idea is to repeat s1 in n1 times, and count how many s2 we c
I was enlightened by the @shawngao's brute force solution, the post can be found [here](https://discuss.leetcode.com/topic/70707/ugly-java-brute-force-solution-but-accepted-1088ms).\n\nThe basic idea is to repeat s1 in n1 times, and count how many s2 we can find. The answer number of s2  we can find divide by n2. \n\nTo accelerate the process, a map is used to find "loop".\n\nThe following is the code\n\nPoint[][] map is used for find loop.\nint[] p1 and int[] p2 are the counters.\n\n```\npublic class Solution {\n\n    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {\n        int len1 = s1.length();\n        int len2 = s2.length();\n        Point[][] map = new Point[len1][len2];\n        int[] p1 = new int[2];\n        int[] p2 = new int[2];\n        while (p1[1] < n1) {\n            char c = s2.charAt(p2[0]);\n            while (p1[1] < n1 && s1.charAt(p1[0]) != c) {\n                inc(p1, len1);\n            }\n            if (map[p1[0]][p2[0]] == null) {\n                map[p1[0]][p2[0]] = new Point(p1[1], p2[1]);\n            } else {\n                int deltaP1 = p1[1] - map[p1[0]][p2[0]].x;\n                int deltaP2 = p2[1] - map[p1[0]][p2[0]].y;\n                int k = (n1 - deltaP1 - 1) / deltaP1;\n                p1[1] += k * deltaP1;\n                p2[1] += k * deltaP2;\n            }\n            inc(p1, len1);\n            inc(p2, len2);\n        }\n        return p2[1] / n2;\n    }\n\n    public void inc(int[] p, int len) {\n        if (++ p[0] == len) {\n            p[0] = 0;\n            p[1] += 1;\n        }\n    }\n}\n```
[]