bzoj 2780 [Spoj]8093 Sevenk Love Oimaster

内容

Description

Oimaster and sevenk love each other.

But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman’s nature, sevenk felt angry and began to check oimaster’s online talk with ChuYuXun. Oimaster talked with ChuYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, “how many strings in oimaster’s online talk contain this string as their substrings?”

Input

There are two integers in the first line,
the number of strings n and the number of questions q.
And n lines follow, each of them is a string describing oimaster’s online talk.
And q lines follow, each of them is a question.
n<=10000, q<=60000
the total length of n strings<=100000,
the total length of q question strings<=360000

Output

For each question, output the answer in one line.

Sample Input

3 3

abcabcabc

aaa

aafe

abc

Sample Output

题解

题意就是给n个串和m个串，求这m个串是n个串中多少个串的子串。

n个串建个广义后缀自动机，注意建的时候对于每个点标记一下这个点有多少个串用了这个点，多个串的化就外挂一个链表。

然后对每个询问串在自动机上匹配，匹配到的点其Parent树子树中的节点就可以包含这个串。我们把Parent树的dfs序找出来，那么这个题就转换成了hh的项链那个题，搞个树状数组就解决了。

这题一遍过样例一遍a，很爽

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;
struct Graph_Chain
{
    struct edge
    {
        int to,next;
    }e[N];
    int st[N],tot;
    void add(int x,int y)
    {
        e[++tot].next=st[x];
        e[tot].to=y,st[x]=tot;
    }
    int dfn[N],dfs_id,pos[N],low[N];
    void dfs(int now)
    {
        dfn[now]=++dfs_id,pos[dfs_id]=now;
        for (int i=st[now];i;i=e[i].next)
            dfs(e[i].to);
        low[now]=dfs_id;
    }
}g,chain;
struct asks
{
    int l,r,id;
}ask[N];
bool comp(asks a,asks b)
{
    return a.r<b.r;
}
struct SAM
{
    int dis[N<<1],fa[N<<1],ch[N<<1][26],sz,root,last;
    void init(){sz=1,root=1,last=root;}
    void insert(int x,int t)
    {
        int now=ch[last][x],pre=last;
        if (now)
            if (dis[now]==dis[pre]+1) last=now;
            else
            {
                int nows=++sz;dis[nows]=dis[pre]+1;
                memcpy(ch[nows],ch[now],sizeof ch[now]);
                fa[nows]=fa[now],fa[now]=nows;
                for (;pre && ch[pre][x]==now;pre=fa[pre]) ch[pre][x]=nows;
                last=nows;
            }
        else
        {
            now=++sz,dis[now]=dis[pre]+1;last=now;
            for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
            if (!pre) fa[now]=root;
            else if (dis[ch[pre][x]]==dis[pre]+1) fa[now]=ch[pre][x];
            else
            {
                int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
                memcpy(ch[nows],ch[q],sizeof ch[nows]);
                fa[nows]=fa[q],fa[q]=fa[now]=nows;
                for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
            }
        }
        chain.add(last,t);
    }
    void ins(char s[],int t)
    {
        int len=strlen(s+1);
        last=root;
        for (int i=1;i<=len;i++)
            insert(s[i]-'a',t);
    }
    void match(char s[],int t)
    {
        int now=root,len=strlen(s+1);
        for (int i=1;i<=len;i++)
            if (ch[now][s[i]-'a'])
                now=ch[now][s[i]-'a'];
            else {now=0;break;}
        ask[t]=(asks){g.dfn[now],g.low[now],t};
    }
}sam;
struct BIT
{
    #define lowbit(x) (x&(-x))
    int c[N];
    void add(int x,int v)
    {
        if (!x) return;
        for (;x<=sam.sz;x+=lowbit(x)) c[x]+=v;
    }
    int sum(int x)
    {
        int ans=0;
        for (;x;x-=lowbit(x)) ans+=c[x];
        return ans;
    }
    int query(int l,int r)
    {
        return sum(r)-sum(l-1);
    }
    #undef lowbit
}bit;
int ans[N],vis[N],n,m;
char s[360010];
main()
{
    sam.init();
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%s",s+1),sam.ins(s,i);
    for (int i=1;i<=sam.sz;i++)
        g.add(sam.fa[i],i);
    g.dfs(1);
    for (int i=1;i<=m;i++)
        scanf("%s",s+1),sam.match(s,i);
    sort(ask+1,ask+1+m,comp);
    int top;
    for (top=1;top<=m&&!ask[top].l;top++);
    for (int i=1;i<=sam.sz;i++)
    {
        int now=g.pos[i];
        for (int j=chain.st[now];j;j=chain.e[j].next)
        {
            int v=chain.e[j].to;
            bit.add(i,1);
            if (vis[v]) bit.add(vis[v],-1);
            vis[v]=i;
        }
        for (;ask[top].r==i;top++)
            ans[ask[top].id]=bit.query(ask[top].l,ask[top].r);
    }
    for (int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}