分析

可以说是关于 自动机运用的较难题了。但是能用 坚决不用 自动机。我们考虑一个串作为字串出现在其它字符串中，那么就是看这个串的结束节点的 集合有多少这个区间的串。所以现在的思路就是，对所有串建一个广义后缀自动机，这里不能建那种 之后就不管的伪自动机。要使用 树建法，或者在线建法。然后对于所有等价类求出 集合，最后查询一个区间和。那么我们发现算法的瓶颈在于如何求出 集合和区间和。我们考虑线段树合并，这样总的复杂度为 。

• 其实这道题用 自动机来写是非常有意思的，可以试试啊。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  const int N = 410000;
  int n,m,rt[N],pos[N];
  char S[N];
  vector<int> G[N];
  int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
  }
  struct SAM{
    int last,size;
    struct Node{
        int len,link,nxt[26];
    }st[N<<1];
    void init() {st[0].link = -1;size++;}
    int insert(int c) {
        if(st[last].nxt[c]) {
            int p = last,q = st[p].nxt[c];
            if(st[p].len + 1 == st[q].len) return q;
            else {
                int cl = size++;st[cl].len = st[p].len + 1;
                st[cl].link = st[q].link;
                for(int i = 0;i < 26;i++) st[cl].nxt[i] = st[q].nxt[i];
                while(p != -1 && st[p].nxt[c] == q) {
                    st[p].nxt[c] = cl;p = st[p].link;
                }
                st[q].link = cl; return cl;
            }
        }
        int cur = size++;st[cur].len = st[last].len + 1;
        int p = last;while(p != -1 && !st[p].nxt[c]) {
            st[p].nxt[c] = cur;p = st[p].link;
        }if(p == -1) st[cur].link = 0;
        else {
            int q = st[p].nxt[c];if(st[q].len == st[p].len + 1) st[cur].link = q;
            else {
                int cl = size++;st[cl].len = st[p].len + 1;
                st[cl].link = st[q].link;
                for(int i = 0;i < 26;i++) st[cl].nxt[i] = st[q].nxt[i];
                while(p != -1 && st[p].nxt[c] == q) st[p].nxt[c] = cl,p = st[p].link;
                st[q].link = st[cur].link = cl;
            }
        }
        return cur;
    }
  }s;
  struct  SegmentTree{
    int lc[N*20],rc[N*20],cnt[N*20];
    int size;
    void insert(int &u,int l,int r,int pos) {
        if(!u) u = ++size;cnt[u]++;if(l == r) return;
        int mid = l + r >> 1;if(pos <= mid) insert(lc[u],l,mid,pos);
        else insert(rc[u],mid+1,r,pos);
    }
    int query(int u,int l,int r,int L,int R) {
        if(!u) return 0;
        if(L <= l && r <= R) return cnt[u];
        if(l > R || r < L) return 0;int mid = l + r >> 1;
        return query(lc[u],l,mid,L,R) + query(rc[u],mid+1,r,L,R);
    }
    int merge(int a,int b,int l,int r) {
        if(!a || !b) return a|b;
        int i = ++size;
        cnt[i] = cnt[a] + cnt[b];
        if(l == r) return i;int mid = l + r >> 1;
        lc[i] = merge(lc[a],lc[b],l,mid);
        rc[i] = merge(rc[a],rc[b],mid+1,r);
        return i;
    }
  }T;
  void dfs(int x) {
    for(auto y : G[x]) {dfs(y);rt[x] = T.merge(rt[x],rt[y],1,n);}
  }
  int main() {
    n = read();m = read();s.init();
    for(int i = 1;i <= n;i++) {
        scanf("%s",S + 1);
        int len = strlen(S + 1);
        s.last = 0;for(int j = 1;j <= len;j++)
        {s.last = s.insert(S[j]-'a');T.insert(rt[s.last],1,n,i);}
        pos[i] = s.last;
    }
    for(int i = 1;i < s.size;i++) G[s.st[i].link].push_back(i);
    dfs(0);rt[0] = 0;
    while(m--) {
        int l = read(),r = read(),id = read();
        int ans = T.query(rt[pos[id]],1,n,l,r);
        printf("%d\n",ans);
    }
    return 0;
  }