@n2c

class Solution {
public int repeatedStringMatch(String A, String B) {
for (String C = A; C.length() < B.length() + A.length()*2; C += A)
if (C.contains(B)) return C.length()/A.length();
return -1;
}
// Stop condition: len(C) >= len(B)+len(A)*2
//
// Why?
//
// Case 1: len(A) >= len(B).
// We claim that:
// If B can be matched, B must be a substring of C (A+A):
// len(C) = len(A) + len(A)
// That's, to judge B matchable, we need to repeat C from A to AA,
// until len(C) = len(A)*3 > len(A)*2.
// On the other hand, len(A) >= len(B) >= 1.
// So, we have len(C) = len(A)*3 >= len(B)+len(A)*2 > len(A)*2,
// i.e. when len(C) >= len(B)+len(A)*2, we can stop repeating C.
// More detailly,
// A = XYZ
// AA = XYZXYZ = C
// AAA = XYZXYZXYZ
// A...AA = XYZ...XYZXYZ
// We observe:
// YZX, ZXY and all their substrings, are always contained by XYZXYZ.
// If C is repeated with 3 or more A, we cannot find a new pattern of substring whose length is <= len(B).
//
//
// Case 2: len(A) < len(B).
// len(B) <= len(C') < len(B) + len(A)
// (Because any string cannot contain a substring longer than the string itself.)
// We claim that:
// If B can be matched, B must be a substring of C (C'+A = A+...+A+A):
// len(B) + len(A) <= len(C) = len(C') + len(A) < len(B) + len(A)*2
// That's, to judge B matchable, we need to repeat C from A to AA,..., and to A...AA,
// until len(C) >= len(B) + len(A)*2.
// More detailly,
// A = XYZ
// A...A = XYZ...XYZ = C'
// A...AA = XYZ...XYZXYZ = C
//
// Case 2.1: len(B) = len(C')
// YZ...XYZX = B or,
// Z...XYZXY = B
// We observe:
// YZ...XYZX, Z...XYZXY and all their substrings, are always contained by XYZ...XYZXYZ.
// If C is repeated with one more A, we cannot find a new pattern of substring whose length is <= len(B).
//
// Case 2.2: len(B) < len(C')
// YZ...XYZ = B or,
// Z...XYZX = B
// We observe:
// YZ...XYZ is contained by YZ...XYZX,
// Z...XYZX is contained by Z...XYZXY.
// From Case 2.1, we know YZ...XYZX, Z...XYZXY and all their substrings, are always contained by XYZ...XYZXYZ.
// Similarly, we don't have to repeat C with one more A. No new pattern of substring is to be discovered.
//
// Discussion:
// Can C' instead of C contain B because len(C') is already > len(B) ?
// Unfortunately, NO!
// Consider: A=XYZ, B=ZXYZXYZA, C'=XYZXYZXYZ, len(B)=8<9=len(C'), but C' cannot contain B.
//
// Summary:
//
// For both case 1 and case 2:
// The stop condition is -- len(C) >= len(B) + len(A)*2
//
}