686. Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note: The length of A and B will be between 1 and 10000.

int repeatedStringMatch(string A, string B) { // time: O(n1 * n2); space: O(n2)
    int n1 = A.size(), n2 = B.size(), cnt = 1;
    string t = A;
    while (t.size() < n2) {
        t += A;
        ++cnt;
    }
    if (t.find(B) != string::npos) return cnt;
    t += A;
    return (t.find(B) != string::npos) ? ++cnt : -1;
}

int repeatedStringMatch(string A, string B) { // time: O(n1 * n2); space: O(n2)
    int n1 = A.size(), n2 = B.size();
    string t = A;
    for (int cnt = 1; cnt <= n2 / n1 + 2; ++cnt) {
        if (t.find(B) != string::npos) return cnt;
        t += A;
    }
    return -1;
}

int repeatedStringMatch(string A, string B) { // time: O(n1 * n2); space: O(n2)
    int n1 = A.size(), n2 = B.size();
    for (int i = 0; i < n1; ++i) {
        int j = 0;
        while (j < n2 && A[(i + j) % n1] == B[j]) ++j;
        if (j == n2) return (i + j - 1) / n1 + 1;
    }
    return -1;
}