<p>Given a binary string <code>s</code> and an integer <code>k</code>, return <code>true</code> <em>if every binary code of length</em> <code>k</code> <em>is a substring of</em> <code>s</code>. Otherwise, return <code>false</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;00110110&quot;, k = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> The binary codes of length 2 are &quot;00&quot;, &quot;01&quot;, &quot;10&quot; and &quot;11&quot;. They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;0110&quot;, k = 1
<strong>Output:</strong> true
<strong>Explanation:</strong> The binary codes of length 1 are &quot;0&quot; and &quot;1&quot;, it is clear that both exist as a substring. 
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;0110&quot;, k = 2
<strong>Output:</strong> false
<strong>Explanation:</strong> The binary code &quot;00&quot; is of length 2 and does not exist in the array.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= 20</code></li>
</ul>


class Solution {
public:
    
    unordered_set<long long> rabin(string &yes,long long sz){
        long long h_s=0,h_p=0,p=256,p_p=1,i,j,m=1000000007;
        
        for(i=0;i<sz;i++){
            p_p=(p_p*p)%m;
        }
        unordered_set<long long>st;
        for(i=0;i<yes.size();i++){
            h_p=(h_p*p+(yes[i]+1))%m;
            if(i>=sz)h_p=(m+h_p-((yes[i-sz]+1)*p_p)%m)%m;
            if(i+1>=sz)
            st.insert(h_p);
        }
        return st;
    }
    bool hasAllCodes(string &s, int k) {
        long long h_s=0,h_p=0,p=256,p_p=1,i,j,m=1000000007;
        unordered_set<long long>st=rabin(s,k);
        //if(rabin(s,sz)==false)return false;
        for(i=0;i<(1<<k);i++){
            string ne="";
            for(j=0;j<k;j++){
                
                if(i&(1<<j)){
                    ne='1'+ne;
                }
                else ne='0'+ne;
            }
            h_s=0;
            for(j=0;j<k;j++){
                h_s=(h_s*p+(ne[j]+1)%m)%m;
            }
            if(st.find(h_s)==st.end())return false;
            
        }
        return true;
    }
};
108578