Repeated String Match

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

• Time : O(n + m)
• Space : O(min(n, m))

c++

class Solution{
    vector<int> PI(string& s) {
        int n = s.length();
        vector<int> pi(n);
        for(int i = 1, j = 0; i < n; i++) {
            while(j > 0 and s[i] != s[j]) j = pi[j - 1];
            if(s[i] == s[j]) pi[i] = ++j;
        }
        return pi;
    }
    int kmp(string s, string& t) {
        int n = s.length(), m = t.length();
        vector<int> pi = PI(t);
        for(int i = 0, j = 0; i < n; i++) {
            while(j > 0 and s[i] != t[j]) j = pi[j - 1];
            if(s[i] == t[j]) {
                if(++j == m) {
                    return i;
                }
            }
        }
        return -1;
    }
public:
    int repeatedStringMatch(string A, string B) {
        int n = A.length(), m = B.length();
        if(n == m) return A == B ? 1 : -1;
        if(n > m) return kmp(A, B) != -1 ? 1 : kmp(A + A, B) != -1 ? 2 : -1;
        int pos = kmp(B, A);
        if(pos == -1) return -1;
        int left = pos - n;
        if(left >= n) return -1;
        int res = 1 + (left >= 0);
        for(int i = n - 1; i >= 0 and left >= 0; i--, left--) {
            if(A[i] != B[left]) return -1;
        }
        for(int i = pos + 1, j = 0; i < m; i++) {
            if(j == 0) res++;
            if(A[j] != B[i]) return -1;
            j = (j + 1) % n;
        }
        return res;
    }
};