686

class Solution {
public:
    vector<int> lps;
    void kmpPreprocess(string pat){
        int i=0, j=-1, n=pat.size();
        lps.resize(n+1, 0);
        lps[0] = -1;
        while(i < n){
            while(j>=0 && pat[i] != pat[j])
                j = lps[j];
            i++; j++;
            lps[i] = j;
        }
    }

    int match(string txt, string pat){
        int n=txt.size(), i=0, cnt=1, j=0, prevj=0;

        while(true){
            while(j>=0 && txt[i] != pat[j])
                j = lps[j];
            i++; j++;
            if(j == pat.size()){
                return cnt;
            }
            if(i == n){
                cnt++;
                i = 0;
                if(j <= prevj)
                    return -1;
                prevj = j;
            }
        }
        return cnt;
    }

    int repeatedStringMatch(string a, string b) {
        kmpPreprocess(b);
        return match(a, b);
    }
};