BZOJ-2780: [Spoj]8093 Sevenk Love Oimaster

[文章目录]

Description

给你n个串,和q组询问,每次询问一个字符串是多少个串的子串。n<=10^4,串长和<=10^5,q<=6*10^4,串长和<=36*10^4

广义后缀自动机,将每个串的后缀树的每个节点+1。查询的时候直接到后缀自动机中拿出答案即可。据说时间复杂度极限是O(n√n) 的???
想要nlogn的话可以把后缀树拿出来做树链的并了,不过我懒。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
int n,m,l[11000],r[11000];
int last=1,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],siz[N<<1],vis[N<<1];
char st[N<<2];
void insert(int x)
{
    int p=last;
    if(ch[p][x])
    {
        int q=ch[p][x];
        if(dep[q]==dep[p]+1) last=q;
        else
        {
            int clo=++tot; last=clo;
            memcpy(ch[clo],ch[q],sizeof(ch[q]));
            pre[clo]=pre[q],dep[clo]=dep[p]+1,pre[q]=clo;
            for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
        }
    }
    else
    {
        int cur=++tot;
        last=cur; dep[cur]=dep[p]+1;
        for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
        if(!p) pre[cur]=1;
        else
        {
            int q=ch[p][x];
            if(dep[q]==dep[p]+1) pre[cur]=q;
            else
            {
                int clo=++tot;
                memcpy(ch[clo],ch[q],sizeof(ch[q]));
                dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
                for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
            }
        }       
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,p,k,len;
    for(i=1;i<=n;++i)
    {
        l[i]=r[i-1]+1;
        scanf("%s",st+l[i]);
        r[i]=strlen(st+1); last=1;
        for(j=l[i];j<=r[i];++j) insert(st[j]-'a');
    }
    for(i=1;i<=n;++i)
        for(p=1,j=l[i];j<=r[i];++j)
        {
            p=ch[p][st[j]-'a'];
            for(k=p;k&&vis[k]!=i;k=pre[k]) vis[k]=i,siz[k]++;
        }
    while(m--)
    {
        scanf("%s",st+1);
        len=strlen(st+1); j=1;
        for(i=1;i<=len;++i) j=ch[j][st[i]-'a'];
        if(i!=len+1) puts("0");
        else printf("%d\n",siz[j]);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注