<p>Given two strings <code>a</code> and <code>b</code>, return <em>the minimum number of times you should repeat string </em><code>a</code><em> so that string</em> <code>b</code> <em>is a substring of it</em>. If it is impossible for <code>b</code>​​​​​​ to be a substring of <code>a</code> after repeating it, return <code>-1</code>.</p>

<p><strong>Notice:</strong> string <code>&quot;abc&quot;</code> repeated 0 times is <code>&quot;&quot;</code>, repeated 1 time is <code>&quot;abc&quot;</code> and repeated 2 times is <code>&quot;abcabc&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;abcd&quot;, b = &quot;cdabcdab&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> We return 3 because by repeating a three times &quot;ab<strong>cdabcdab</strong>cd&quot;, b is a substring of it.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;a&quot;, b = &quot;aa&quot;
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>4</sup></code></li>
	<li><code>a</code> and <code>b</code> consist of lowercase English letters.</li>
</ul>

// Jai shree ram
class Solution {
private:
std::vector<int> buildPrefixTable(const std::string &pattern) {
    int m = pattern.size();
    std::vector<int> prefixTable(m, 0);
    int j = 0;

    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefixTable[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        prefixTable[i] = j;
    }

    return prefixTable;
}


 
 bool KMP(const std::string &text, const std::string &pattern) {
    if (pattern.empty()) {
        return true; // Empty pattern is always a substring
    }

    int n = text.size();
    int m = pattern.size();
    std::vector<int> prefixTable = buildPrefixTable(pattern);
    int j = 0;

    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = prefixTable[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            return true; // Pattern found
        }
    }

    return false; // Pattern not found
}
public:
    int repeatedStringMatch(string a, string b) {

        if (b == a) return 1;
        int n = a.size();
        int m = b.size();

        int lo = 0, hi = abs(m-n)+100;

        while(lo <= hi)
        {
            int mid = lo + (hi - lo)/ 2;
            string ss = "";
            for(int i = 0; i < mid; i++)
            {
                ss += a;
            }

            if (KMP(ss, b))
            {
                hi = mid - 1;
            }
            else lo = mid + 1;

        }

            string ss = "";
            for(int i = 0; i < lo; i++)
            {
                ss += a;
            }

            if (KMP(ss, b))
            {
                return lo;
            }
            else return -1;

    }
};
42234