// even simple than kmp
void build() {
    for (int i = 0; i < 26; i++) if (tr[0][i]) q[++tt] = tr[0][i];
    while (tt >= hh) {
        int t = q[hh++];
        for (int i = 0; i < 26; i++) {
            int &p = tr[t][i], q = tr[ne[t]][i];
            if (!p) p = q;
            else ne[p] = q;
        }
        q[++tt] = p;
    }
}

// same as trie
void insert(string s) {
    int p = 0;
    for (auto c : s) {
        if (!tr[p][c]) tr[p][c] = ++idx;
    }
    cnt[p]++;
}