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

class Solution {
public:

    #define pii pair <int, int>
    #define nd second
    #define st first

    struct node {
        node* nxt[26];
        int id, cnt; 
        node() {
            for (int i = 0; i < 26; i ++)
                nxt[i] = NULL;
            id = -1;
            cnt = 0;
        }

        node* edge(char ch) {
            return nxt[ch - 'a'];
        }

        void set(char ch) {
            nxt[ch - 'a'] = new node();
        }
    };

    struct trie {
        node* root;
        int depth;
        trie(int d) {
            root = new node();
            depth = d;
        }

        void dfs(node* u) {
            for (int i = 'a'; i <= 'z'; i ++) {
                if (u->edge(i))
                    dfs(u->edge(i));
            }
            delete u;
        }

        ~trie() {
            dfs(root);
        }

        void insert(string &word, int v) {
            node* cur = root;
            for (char ch: word) {
                if (cur->edge(ch) == NULL)
                    cur->set(ch);
                
                cur = cur->edge(ch);
            }
            cur->id = v;
            cur->cnt ++;
        }

        pii search(string &s, int l, int r) {
            node* cur = root;
            if (!cur) return  {0, 0};
            for (int i = l; i <= r; i ++) {
                cur = cur->edge(s[i]);
                if (!cur) return {0, 0};
            }
            return {cur->id, cur->cnt};
        }
    };

    vector<int> findSubstring(string s, vector<string>& words) {
        int n = s.size(), m = words.size(), d = words[0].size();
        trie myTrie(d);

        for (int i = 0; i < m; i ++)
            myTrie.insert(words[i], i + 1);

        vector <int> ids, cnt(m + 1);
        for (int i = 0; i + d - 1 < n; i ++) {
            pii tmp = myTrie.search(s, i, i + d - 1);
            ids.push_back(tmp.st);
            if (tmp.st > 0) cnt[tmp.st] = tmp.nd;
        }

        int tot = 0;
        for (int i: cnt) if (i) tot ++;

        vector <int> ans;
        for (int i = 0; i < d; i ++) {
            vector <int> mp(m + 1);
            int cur = 0;
            
            for (int j = i; j < ids.size(); j += d) {
                if (++ mp[ids[j]] == cnt[ids[j]]) cur ++;
                if (mp[ids[j]] - 1 == cnt[ids[j]]) cur --;
                if (j >= m * d) {
                    int id = ids[j - m * d];
                    if (-- mp[id] == cnt[id]) cur ++;
                    if (mp[id] + 1 == cnt[id]) cur --;
                }

                if (cur == tot && j >= (m - 1) * d) ans.push_back(j - (m - 1) * d);
            }
        }

        return ans;
    }
};
36387