<p>You are given a string <code>s</code> and an array of strings <code>words</code>. All the strings of <code>words</code> are of <strong>the same length</strong>.</p>

<p>A <strong>concatenated string</strong> is a string that exactly contains all the strings of any permutation of <code>words</code> concatenated.</p>

<ul>
	<li>For example, if <code>words = [&quot;ab&quot;,&quot;cd&quot;,&quot;ef&quot;]</code>, then <code>&quot;abcdef&quot;</code>, <code>&quot;abefcd&quot;</code>, <code>&quot;cdabef&quot;</code>, <code>&quot;cdefab&quot;</code>, <code>&quot;efabcd&quot;</code>, and <code>&quot;efcdab&quot;</code> are all concatenated strings. <code>&quot;acdbef&quot;</code> is not a concatenated string because it is not the concatenation of any permutation of <code>words</code>.</li>
</ul>

<p>Return an array of <em>the starting indices</em> of all the concatenated substrings in <code>s</code>. You can return the answer in <strong>any order</strong>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;barfoothefoobarman&quot;, words = [&quot;foo&quot;,&quot;bar&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,9]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substring starting at 0 is <code>&quot;barfoo&quot;</code>. It is the concatenation of <code>[&quot;bar&quot;,&quot;foo&quot;]</code> which is a permutation of <code>words</code>.<br />
The substring starting at 9 is <code>&quot;foobar&quot;</code>. It is the concatenation of <code>[&quot;foo&quot;,&quot;bar&quot;]</code> which is a permutation of <code>words</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;wordgoodgoodgoodbestword&quot;, words = [&quot;word&quot;,&quot;good&quot;,&quot;best&quot;,&quot;word&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[]</span></p>

<p><strong>Explanation:</strong></p>

<p>There is no concatenated substring.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;barfoofoobarthefoobarman&quot;, words = [&quot;bar&quot;,&quot;foo&quot;,&quot;the&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[6,9,12]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substring starting at 6 is <code>&quot;foobarthe&quot;</code>. It is the concatenation of <code>[&quot;foo&quot;,&quot;bar&quot;,&quot;the&quot;]</code>.<br />
The substring starting at 9 is <code>&quot;barthefoo&quot;</code>. It is the concatenation of <code>[&quot;bar&quot;,&quot;the&quot;,&quot;foo&quot;]</code>.<br />
The substring starting at 12 is <code>&quot;thefoobar&quot;</code>. It is the concatenation of <code>[&quot;the&quot;,&quot;foo&quot;,&quot;bar&quot;]</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 30</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of lowercase English letters.</li>
</ul>

#define ll long long
ll p1 = 31;
ll mod = 1e9 + 7;

class Solution {
    vector<ll> precompute_powers(int length) {
        vector<ll> powers(length);
        powers[0] = 1;
        for (int i = 1; i < length; ++i) {
            powers[i] = (powers[i-1] * p1) % mod;
        }
        return powers;
    }

    ll hash(const string &s, int start, int length, const vector<ll> &powers) {
        ll h = 0;
        for (int i = 0; i < length; ++i) {
            h = (h + (s[start + i] - 'a' + 1) * powers[i]) % mod;
        }
        return h;
    }

public:
    vector<int> findSubstring(string s, vector<string>& w) {
        int n = s.size();
        int x = w[0].size();
        int len = w.size() * x;

        if (n < len) return {};

        unordered_map<ll, int> mp;
        vector<ll> powers = precompute_powers(len);

        for (const auto &word : w) {
            mp[hash(word, 0, x, powers)]++;
        }

        vector<ll> p(n - x + 1);
        for (int i = 0; i <= n - x; ++i) {
            p[i] = hash(s, i, x, powers);
        }

        vector<int> ans;
        for (int i = 0; i <= n - len; ++i) {
            unordered_map<ll, int> mp2 = mp;
            int j = i;
            int cnt = 0;

            while (j < i + len) {
                ll h = p[j];
                if (mp2[h]) {
                    mp2[h]--;
                    cnt++;
                } else {
                    break;
                }
                j += x;
            }

            if (cnt == w.size()) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};
// it is giving mle on 175 testcase 
// 
// #define ll long
// ll p1 = 31; 
// ll p2 = 37;
// ll mod = 1e9 + 7;
// class Solution {
//     ll hash1(string s ,  int i , int x  ){
//         ll h = 0 ; 
//         ll t  = p1;
//         for(int k = i; k < i+x ; k++){
//          h = (h + ((s[k] - 'a' + 1)*t)%mod)%mod ; 
//          t = (t* p1)%mod;
//         }
//         return h ; 
//     }
//       ll hash2(string s ,  int i , int x  ){
//         ll h = 0 ; 
//         ll t  = p2;
//         for(int k = i; k <i+x ; k++){
//          h = (h + ((s[k] - 'a' + 5)*t)%mod) %mod; 
//          t = (t* p2)%mod;
//         }
//         return h ; 
//     }
// public:
//     vector<int> findSubstring(string s, vector<string>& w) {
       
//         int x = w[0].length();
//         int n  = s.length();
//         vector<int> p1( n , 0 );
//         vector<int> p2 ( n , 0 );
    
//         for(int i = 0 ; i+x<=n ; i++){
//            p1[i] = (hash1( s , i , x  ))%mod;
//            p2[i] =( hash2( s , i , x) ) %mod;
//         //    r1 = p1[i];
//         //    r2 = p2[i];
//         //    cout<<r1 << " "<<r2 <<endl;
//         }
         
//         ll c1 = 0 ; 
//         ll c2 = 0 ; 
//         ll len = 0 ;
//     //     cout<<" p"<<p1[0] << " "<<p2[0]<<endl;
//     //    cout<<" p"<<p1[4] << " "<<p2[4]<<endl;
//        // multiset<string> r;
//        unordered_map<string,int> r;
//         for(int i = 0 ; i< w.size(); i++){
//             r[w[i]]++;
//             c1 = (c1 + hash1( w[i] , 0 , x ))%mod;
//             c2 = (c2 + hash2(w[i] ,  0 , x))%mod;
//             len += x;
//         }
//        // sort(r.begin() , r.end());
//         // cout<<len<<" len"<<endl;
//         // cout<<"te"<<c1 << " "<<c2<<endl;
//        vector<int> cnt ; 
//        for(int i = 0 ; i+ len <= s.size() ; i++){
//          int j  = i ;
//          ll t1 = 0 ; 
//          ll t2 = 0 ; 
//          unordered_map<string , int> st;
//          while(j< i+ len){
//          t1 = (t1 + p1[j])%mod;
//          t2 = (t2 + p2[j])%mod;
//           st[(s.substr(j , x))]++;
//            j+= x;
           
//          }
//         //  if(i == 6){
//         //     cout<<t1<<" "<< t2<<" "<<c1<<" "<<c2 <<endl;
//         //  }
//          if(t1 == c1 && t2 == c2){
//             // string temp    = s.substr(i , len );
//             // cout<<temp<<" "<<i<<" "<<i+len<<endl;
//             // sort(temp.begin() , temp.end());
//             // cout<<r<<" "<<temp<<endl;
//             // cout<<i<<endl;
//             // for(auto t: st){
//             //     cout<<t<<" ";
//             // }
//             // cout<<endl;
//             // for(auto t: r){
//             //     cout<<t<<" ";
//             // }
//             // cout<<endl;
//             if(st == r){
//             cnt.push_back(i);
//             }
//          }
//        } 
//        return cnt ;
//     }
// };
// #define ll long long int
// ll p = 1;
// ll mod = 1e9+7;

// class Solution {
//     ll kmp(int i , int j , string &s){
//     if(j == -1){
//         j = s.length()-1;
//       }
//      int cnt = 1 ;
//      ll ans  = 0 ;  
//      for(int k = i ; k<=j ; k++){
//        if(cnt == 3){
//          p = 1;
//        }
//        ans = (ans+ p*(s[k] - 'a'+1))%mod;
//        p = (31*p) %mod;
//      }  
//      return ans ;
//     }
//     vector<int> ans ; 
//     vector<bool> vis;
//     int z = 0 ; 
//     void  solve(int i , string s  ){
//      if(i== s.length()){
//         return 0;
//      }

//      if(vis[i]){
//         return ;
//      }

//      if(i+k-1<s.length()){
//         if(kmp(i ,i+k-1 , s) == temp){
//             ans.push_back(i);

//         }
//      }
//      solve(i+1 , s);
//      return ;
//     }
// public:
//     vector<int> findSubstring(string s, vector<string>& words) {
//       // i will take it to give me 
//     }
// };
131787