BZOJ3413:匹配 后缀自动机

思路:

这道题真心是一道字符串好题.我要不是膜拜了秦神的代码现在还看不出个所以然...(果然太弱不解释)

首先呢,题目的意思其实就是让我们求询问串与原串的每一个后缀的LCP之和.但是呢,有一个Trick,那就是找到整个串之后就不找啦!

那么先考虑一种简单的情况,就是原串中并不存在询问串.

那么,我们在逆序后缀树上走,每走到一个位置,就看一下当前串出现了几次.这样,实际上每次统计的都是这一位的贡献.

现在有限制.我们可以预先处理出询问串第一次出现的位置.那么我们可以离线处理,利用dfs序来维护逆序后缀树,然后将所有询问按照限制从小到大累加贡献.

有点不好说.详情见代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
typedef long long LL;
  
#define N 100010
#define M 3000010
#define Q 500010
int tranc[N<<1][10],pa[N<<1],len[N<<1],first[N<<1],ins[N],cnt,root,last;
inline int newnode(int l){
    len[++cnt]=l;return cnt;
}
  
char s[N];
  
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[500010*12],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void flush(){fwrite(buf,1,o-buf,stdout);}
}
using namespace Fio;
  
namespace Tree{
    int head[N<<1],next[N<<1],end[N<<1];
    inline void addedge(int a,int b){
        static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;
    }
    int in[N<<1],out[N<<1],tclock;
    inline void dfs(int x){
        in[x]=++tclock;
        for(int j=head[x];j;j=next[j])dfs(end[j]);
        out[x]=tclock;
    }
    int A[N<<1];
    inline int ask(int x){int r=0;for(;x;x-=x&-x)r+=A[x];return r;}
    inline void mdf(int x,int add){for(;x<=cnt;x+=x&-x)A[x]+=add;}
    inline void addnode(int x){mdf(in[x],1);}
    inline int asksubtree(int x){return ask(out[x])-ask(in[x]-1);}
}
 
namespace Query{
    int head[N],next[M],end[M],lab[M];
    inline void insert(int a,int b,int _lab){
        static int q=1;end[q]=b,next[q]=head[a],head[a]=q,lab[q++]=_lab;
    }
}
  
LL res[Q];
char Read[100010];
  
char ch;
int main(){
    int n;Get(n);register int i,j;
      
    int id=0;while(!digit(ch=getc()));s[++id]=ch;
    while(digit(ch=getc()))s[++id]=ch;  
     
    root=last=newnode(0);
    int p,q,np,nq,y;
    for(i=1;i<=n;++i){
        ins[i]=np=newnode(len[last]+1);
        for(y=s[i]-'0',p=last;p&&!tranc[p][y];p=pa[p])tranc[p][y]=np;
        if(!p)pa[np]=root;
        else{
            q=tranc[p][y];
            if(len[q]==len[p]+1)pa[np]=q;
            else{
                nq=newnode(len[p]+1),pa[nq]=pa[q],pa[q]=pa[np]=nq;
                memcpy(tranc[nq],tranc[q],sizeof tranc[q]);
                for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
            }
        }last=np;
    }
      
 
    for(i=1;i<=n;++i)for(p=ins[i];p;p=pa[p])if(!first[p])first[p]=i;else break;
     
    for(i=1;i<=cnt;++i)if(pa[i])Tree::addedge(pa[i],i);
    Tree::dfs(1);
     
     
     
    int cas;Get(cas);
    for(i=1;i<=cas;++i){
        int len=0;while(!digit(ch=getc()));Read[++len]=ch;
        while(digit(ch=getc()))Read[++len]=ch;
         
        bool find=1;int p=root;
        for(j=1;j<=len;++j){
            y=Read[j]-'0';if(tranc[p][y])p=tranc[p][y];else{find=0;break;}
        }
        if(!find){
            res[i]=n;
            for(p=root,j=1;j<=len;++j){
                y=Read[j]-'0';if(tranc[p][y])p=tranc[p][y],Query::insert(n,p,i);else break;
            }
        }
        else{
            res[i]=first[p]-len;
            int firstins=first[p];
            for(p=root,j=1;j<=len;++j){
                y=Read[j]-'0',Query::insert(firstins-len+j,p=tranc[p][y],i);
            }
        }
    }
     
    for(i=1;i<=n;++i){
        Tree::addnode(ins[i]);
        for(j=Query::head[i];j;j=Query::next[j])res[Query::lab[j]]+=Tree::asksubtree(Query::end[j]);
    }
      
    for(i=1;i<=cas;++i)Fio::print(res[i]);
 
    Fio::flush();
    return 0;
}