CF547E.cpp

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int N = 2e5+10, M = 5e5+10;
#define pb push_back
int n, q;
string s[N];

namespace SGT {
    const int K = 40 * N;
    int idx;
    int ls[K], rs[K];
    i64 sum[K];
    #define Mid ((L+R) >> 1)
    i64 query(int u, int l, int r, int L, int R) {
        if (l <= L && R <= r) return sum[u];
        i64 res = 0;
        if (l <= Mid) res = query(ls[u], l, r, L, Mid);
        if (Mid+1 <= r) res += query(rs[u], l, r, Mid+1, R);
        return res;
    }

    void insert(int& u, int p, int L, int R) {
        if (!u) u = ++idx;
        sum[u]++;
        if (L == R) return;
        if (p <= Mid) insert(ls[u], p, L, Mid);
        else insert(rs[u], p, Mid+1, R);
    }

    int merge(int u, int v, int L, int R) {
        if (!u || !v) return u+v;

        int node = ++idx;
        sum[node] = sum[u] + sum[v];
        if (L == R) return node;

        ls[node] = merge(ls[u], ls[v], L, Mid);
        rs[node] = merge(rs[u], rs[v], Mid+1, R);
        return node;
    }
}

namespace ACAM {
    int tr[N][26], fail[N], idx;
    vector<int> G[N];
    int rt[N], node[N];

    void insert(const string& s, int i) {
        int u = 0;
        for (char c: s) {
            int p = c - 'a';
            if (!tr[u][p]) tr[u][p] = ++idx;
            u = tr[u][p];
            SGT::insert(rt[u], i, 1, n);
        }
        node[i] = u;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);
        while (q.size()) {
            int fa = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                int& u = tr[fa][i];
                if (u) fail[u] = tr[fail[fa]][i], q.push(u);
                else u = tr[fail[fa]][i];
            }
        }
        for (int i = 1; i <= idx; i++) G[fail[i]].pb(i);
    }

    void dfs(int u) {
        for (int to: G[u]) {
            dfs(to);
            rt[u] = SGT::merge(rt[u], rt[to], 1, n);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ACAM::insert(s[i], i);
    }
    ACAM::build();
    ACAM::dfs(0);

    for (int i = 1; i <= q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        
        cout << SGT::query(ACAM::rt[ACAM::node[k]], l, r, 1, n) << '\n';
    }

    return 0;
}