<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 Solution {
public:
    int powermod(int x, int n) {
        int mod = 1e9 + 7;
        long long t = x;
        long long ans = 1;
        while (n) {
            if (n % 2)
                ans *= t;
            ans %= mod;
            t *= t;
            t %= mod;
            n /= 2;
        }
        return (ans % mod);
    }

    const long long m1 = 1e9 + 7;
    int repeatedStringMatch(string& a, string& b) {
        int na = a.size(), nb = b.size();
        long long hb = 0;
        for (int i = 0; i < nb; i++) {
            hb = (hb * 31 + b[i] - 'a' + 1);
            hb %= m1;
        }
       
        long long hw = 0;
        int index = 0;
        int ans = 0;
        for (int i = 0; i < nb; i++) {
            if (index == 0)
                ans++;
            hw = hw * 31 + a[index++] - 'a' + 1;
            hw %= m1;

            index %= na;
        }
           

        int lindex = 0;
       
        cout<<hb<<endl;
        
        long long temp=powermod(31,nb-1);
        while (hw != hb && ans <= (nb / na + 2)) {
            if (index == 0)
                ans++;
            cout<<hw<<endl;
            hw = (hw +m1*27 -(1LL * (a[lindex++] - 'a' + 1) * temp)  ) %m1;
            cout<<hw<<endl;
          
            hw = (hw * 31) % m1;
            cout<<hw<<endl;
            
            hw = (hw + (a[index++] - 'a' + 1)) % m1;
            cout<<hw<<endl;
           
            index %= na;
            lindex %= na;
        }
        if (hw != hb)
            return -1;
        return ans;
    }
};
10095