Codeforces 547E Mike and Friends

虽然堆砌了很多高级数据结构……实际上做法是很 trivial 的（
所以也可以用 ACAM 做（

简单地建出广义 SAM 并记录每个串对应的状态，然后 Parent Tree 上线段树合并维护在每个串中的出现次数（即 endpos 大小），区间查询即可。
隔壁 CF666E 的弱化版（

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5;
int n,q;
char s[N + 5];
int ed[N + 5];
namespace SEG
{
    struct node
    {
        int sum;
        int ls,rs;
    } seg[(N << 5) + 10];
    int seg_tot;
    void insert(int x,int &p,int tl,int tr)
    {
        int &tot = seg_tot;
        !p && (p = ++tot),++seg[p].sum;
        if(tl == tr)
            return ;
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
    }
    int merge(int x,int y)
    {
        if(!x || !y)
            return x | y;
        int &tot = seg_tot;
        int p = ++tot;
        seg[p].sum = seg[x].sum + seg[y].sum;
        seg[p].ls = merge(seg[x].ls,seg[y].ls);
        seg[p].rs = merge(seg[x].rs,seg[y].rs);
        return p;
    }
    int query(int l,int r,int p,int tl,int tr)
    {
        if(!p || (l <= tl && tr <= r))
            return seg[p].sum;
        int mid = tl + tr >> 1;
        int ret = 0;
        l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
        r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
        return ret;
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len,rt;
    } sam[(N << 1) + 5];
    int tot = 1,las = 1;
    inline void insert(int x,int pos)
    {
        if(sam[las].ch[x] && sam[las].len + 1 == sam[sam[las].ch[x]].len)
        {
            SEG::insert(pos,sam[las = sam[las].ch[x]].rt,1,n);
            return ;
        }
        int cur = las,p = ++tot,flag = 0,nxt;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                cur == las && (flag = 1),nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].rt = 0;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        SEG::insert(pos,sam[las = flag ? nxt : p].rt,1,n);
    }
    int c[N + 5],a[(N << 1) + 5];
    inline void init()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= N;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%s",s + 1),SAM::las = 1;
        for(char *p = s + 1;*p;SAM::insert(*p++ - 'a',i));
        ed[i] = SAM::las;
    }
    SAM::init();
    for(int k,l,r;q;--q)
        scanf("%d%d%d",&l,&r,&k),printf("%d\n",SEG::query(l,r,SAM::sam[ed[k]].rt,1,n));
}