<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>

class RabinKarp{
    private:
        vector<long long> prefixHashArray;
        vector<long long> powerArray;
        long long mod = 1e9+7;
        string s;
        string pattern;
        long long target = 0;
        int sn = 0;
        int pn = 0;
    public:
        RabinKarp(string s, string pattern){
            int m = s.size();
            int n = pattern.size();
            this->sn = m;
            this->pn = n;
            this->s = s;
            this->pattern = pattern;

            // prefixHashArray.resize(m+1);
            // powerArray.resize(m+1);

            long long target = hashCode(pattern);
            this->target = target;

        }

        long long hashCode(string &pattern){
            long long code = 0;
            int n = pattern.size();
            long long pow = 1;
            long long p = 31;

            for(char c: pattern){
                int idx = c - 'a' + 1;
                code = (code + (idx)) % mod;
                // pow = (pow*p)%mod;
            }

            return code % mod;
        }

        bool isPatternMatched(string &s, string &p){
            long long sp = 0, ep = this->pn-1;
            int sn = s.size();

            string subStr = s.substr(0, this->pn);
            long long initialCode = hashCode(subStr);

            while(ep < sn )
            {
                if(initialCode == this->target){
                    string currStr = s.substr(sp, ep-sp+1);
                    if(s.substr(sp, ep-sp+1) == p) return true;
                }


                int sub = s[sp] - 'a' + 1;
                sp++;
                ep++;
                int add = s[ep] - 'a' + 1;
                initialCode = initialCode - sub + add;

            }

            return false;

        }
};
class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        RabinKarp rk = RabinKarp(A, B);

        if(A == B) return 1;
        
        int count = 1;
        string source = A;
        while(source.size() < B.size()){
            source+=A;
            count++;
        }
        
        // edge cases
        if(source == B) 
            return count;
        
        if(rk.isPatternMatched(source, B)) return count;

        string cS = source+A;
        if(rk.isPatternMatched(cS, B)) return count+1;

        return -1;


    }
};

//. 0 1 2 3 4 5 6 7 8 9 10 11
//  a b c d a b c d a b c d
//. 0 1 2 3 0 1 2 3 0 1 2 3

23869