Java | 6ms | Find Cycle | O(MN)
Not much to say, find the cycle. It is quite weird it is tagged under DP question. More like cycle detection question.\n\nThis runs in O(MN) because we are boun
Not much to say, find the cycle. It is quite weird it is tagged under DP question. More like cycle detection question.\n\nThis runs in `O(MN)` because we are bound to encounter a cycle in all `M*N` possibilities, and whenever we do, we skip to near the end.\n#### Java\n```Java\nclass Solution {\n    public int getMaxRepetitions(String A, int a, String B, int b) {\n        int m = A.length(), n = B.length();\n        int[][] x = new int[m][n];\n        int[][] y = new int[m][n];\n        for (int i = 1, j = 1; true; i++){\n            int ii = i%m, jj = j%n, xx = x[ii][jj], yy = y[ii][jj];\n            x[ii][jj]=i;\n            y[ii][jj]=j;\n            if (xx > 0){ // ultra jump to the end!\n                int k = (a*m-i)/(i-xx);\n                i += k*(i-xx);\n                j += k*(j-yy);\n            }\n            if (i == a*m){ // reached the end\n                return j/(n*b);\n            }\n            if (A.charAt(ii)==B.charAt(jj)){ // subsequence check\n                j++;\n            }\n        }\n    }\n}\n```
['Java']