Shinbokuow - 不试着去思考的话，不就已经死去了吗

Codechef 12.12 DIFTRIP Trie树+后缀自动机+STL

9 年前

Tags: Trie 后缀自动机 STL
Posted in Something | 0 Comments

Codechef 12.4 TSUBSTR 后缀自动机+Trie

9 年前

Tags: 后缀自动机 Trie
Posted in Something | 0 Comments

BZOJ3998: [TJOI2015]弦论后缀自动机

10 年前

Tags: 后缀树后缀自动机
Posted in BZOJ | 0 Comments

BZOJ3413:匹配后缀自动机

10 年前

思路:

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#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;
}

Tags: 后缀自动机
Posted in BZOJ | 0 Comments

BZOJ2882:工艺 STL+后缀自动机

10 年前

思路:这大概也算是后缀自动机裸题了吧.

虽然最小表示法最靠谱,不过我还是懒,于是用map水了一发.好方便啊~`

注意数据范围有一些不靠谱,详情见代码= =

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
  
#define N 500010
map<int,int>tranc[N<<1];int pa[N<<1],len[N<<1],cnt,root,last;
inline int newnode(int l){
    len[++cnt]=l;return cnt;
}
inline void init(){
    root=last=newnode(0);
}
  
int a[N<<1];
int main(){
    int n;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),a[i+n]=a[i];
    int p,np,q,nq,y;
    for(init(),i=1;i<=n*2;++i){
        np=newnode(len[last]+1);
        for(p=last,y=a[i];tranc[p].find(y)==tranc[p].end();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;
                tranc[nq]=tranc[q];
                for(;p&&tranc[p].find(y)!=tranc[p].end()&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
            }
        }last=np;
    }
    map<int,int>::iterator it;
    for(i=1,p=root;i<=n;++i){
        if(i>1)putchar(' ');
        it=tranc[p].begin();
        printf("%d",it->first);
        p=tranc[p][it->first];
    }
  
    return 0;
}

Tags: STL 后缀自动机
Posted in BZOJ | 0 Comments

BZOJ3277:串后缀自动机+离线处理+树状数组(&&BZOJ3473)

10 年前

思路:

水题一道.

首先建立广义后缀树.

然后利用离线+树状数组搞出每一个节点在多少个串中.

然后如果这个节点在不少于 $k$ 个串中,我们令这个结点的权值为这个节点父亲边的字符个数,否则为0.

随后我们预处理一下从根到每个节点路径上的权值和.

于是每个字符串的答案等于所有这个字符串的后缀节点的从根到该节点的权值和.

时间复杂度 $O(nlogn)$ .

(貌似比一些后缀数组的神方法要好多了QoQ)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define N 100010
  
int tranc[N<<1][26],len[N<<1],pa[N<<1],cnt,root,last;
inline int newnode(int l){len[++cnt]=l;return cnt;}
  
struct Graph{
    int head[N<<1],next[N<<1],end[N<<1],ind;
    inline void addedge(int a,int b){int q=++ind;end[q]=b,next[q]=head[a],head[a]=q;}
}w,g,sav;
  
char s[N];
  
int seq[N<<1],in[N<<1],out[N<<1],tclock;
inline void dfs(int x){
    in[x]=++tclock,seq[tclock]=x;
    for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
    out[x]=tclock;
}
  
struct Ask{
    int lab,l,r;
    Ask(){}
    Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
    bool operator<(const Ask&B)const{return r<B.r;}
}S[N<<1];
  
int ans[N<<1],lastins[N];
  
int A[N<<1];
inline void mdf(int x,int add){
    for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
    int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
  
int v[N<<1];
  
void dfs2(int x){
    v[x]+=v[pa[x]];
    for(int j=g.head[x];j;j=g.next[j])dfs2(g.end[j]);
}
  
void get(int x){
    for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");
}
  
int main(){
    int n,lim;scanf("%d%d",&n,&lim);
      
    register int i,j,k;int y;int p,np,q,nq,rep,tmp;
    for(root=newnode(0),i=1;i<=n;++i){
        scanf("%s",s);int l=strlen(s);
        for(last=root,j=l-1;j>=0;--j){
            if((p=tranc[last][y=s[j]-'a'])!=0){
                if(len[p]==len[last]+1)last=p;
                else{
                    rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
                    memcpy(tranc[rep],tranc[p],sizeof tranc[p]);
                    for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
                    last=rep;
                }
            }
            else{
                np=newnode(len[last]+1);
                for(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[np]=pa[q]=nq;
                        memcpy(tranc[nq],tranc[q],sizeof tranc[q]);
                        for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
                    }
                }last=np;
            }
            w.addedge(last,i);
            sav.addedge(i,last);
        }
    }
      
    for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
    dfs(1);
      
    for(i=1;i<=cnt;++i)S[i]=Ask(i,in[i],out[i]);sort(S+1,S+cnt+1);
    for(k=i=1;i<=cnt;++i){
        for(j=w.head[seq[i]];j;j=w.next[j]){
            if(lastins[w.end[j]])mdf(lastins[w.end[j]],-1);mdf(lastins[w.end[j]]=i,1);
        }
        for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
    }
      
    for(i=1;i<=cnt;++i)v[i]=ans[i]>=lim?len[i]-len[pa[i]]:0;
      
    dfs2(1);
      
    long long nowans;
    for(i=1;i<=n;++i){
        if(i>1)putchar(' ');
        for(nowans=0,j=sav.head[i];j;j=sav.next[j])nowans+=v[sav.end[j]];
        printf("%lld",nowans);
    }
      
    return 0;
}

Tags: 后缀自动机离线处理树状数组 dfs序
Posted in BZOJ | 0 Comments

BZOJ1396:识别子串后缀自动机+并查集(&&BZOJ2865)

10 年前

思路:

我们建立原串的后缀树,那么发现出现次数为1的子串仅能出现在叶子节点上的父亲边上.(说起来很容易)

然后发现每一个更新可以分解为两端,每一段可以相当于一条斜率恒定的线段.

因此我们将两段分开,按照截距从小到大排序,并用并查集模拟覆盖即可.

(说起来很容易)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define N 100010
struct Node{
    Node*tranc[26],*pa;int len,begin,siz,deg;
    Node(){}
    Node(int _len,int _begin):len(_len),begin(_begin){}
}Tnull,*null=&Tnull,mem[N<<1],*P=mem,*root,*last;
Node*Newnode(int _len,int _begin){
    P->len=_len,P->begin=_begin;for(int i=0;i<26;++i)P->tranc[i]=null;P->pa=null;return P++;
}
  
char s[N];
  
struct Interval{
    int l,r,k;
    Interval(){}
    Interval(int _l,int _r,int _k):l(_l),r(_r),k(_k){}
    bool operator<(const Interval&B)const{return k<B.k;}
}S[N],S2[N];
  
int r[N];
inline void reset(int n){
    for(register int i=1;i<=n+1;++i)r[i]=i;
}
inline int find(int x){
    int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;
}
  
int v[N],vv[N];
  
Node*q[N<<1];int fr,ta;
  
int main(){
    scanf("%s",s+1);int l=strlen(s+1);
    register int i,j;int y;Node*p,*np,*q,*nq;
    for(last=root=Newnode(0,0),i=l;i>=1;--i){
        np=Newnode(last->len+1,i);np->siz=1;
        for(p=last,y=s[i]-'a';p!=null&&p->tranc[y]==null;p=p->pa)p->tranc[y]=np;
        if(p==null)np->pa=root;
        else{
            q=p->tranc[y];
            if(q->len==p->len+1)np->pa=q;
            else{
                nq=Newnode(p->len+1,0);nq->pa=q->pa,q->pa=np->pa=nq;
                memcpy(nq->tranc,q->tranc,sizeof q->tranc);
                for(;p!=null&&p->tranc[y]==q;p=p->pa)p->tranc[y]=nq;
            }
        }last=np;
    }
      
    for(p=mem;p<P;++p)++p->pa->deg;
    for(p=mem;p<P;++p)if(p->deg==0)::q[ta++]=p;
    while(fr^ta){
        p=::q[fr++];
        if(p->pa!=null){
            p->pa->siz+=p->siz;
            if(!--p->pa->deg)
                ::q[ta++]=p->pa;
        }
    }
      
    int id=0,id2=0;
    for(p=mem;p<P;++p){
        if(p->siz==1){
            //printf("%d %d %d\n",p->begin,p->len,p->pa->len);
            S[++id]=Interval(l-(p->len-p->pa->len)+1,l,1-p->begin);
            S2[++id2]=Interval(p->begin,S[id].l-1,S[id].l-p->begin+1);
        }
    }sort(S+1,S+id+1),sort(S2+1,S2+id2+1);
      
    reset(l);
    memset(v,0x3f,sizeof v);
    for(i=1;i<=id;++i){
        for(j=find(S[i].l);j<=S[i].r;j=r[j]){
            if(v[j]==0x3f3f3f3f)v[j]=S[i].k;
            r[j]=find(j+1);
        }
    }
    reset(l);
    memset(vv,0x3f,sizeof vv);
    for(i=1;i<=id2;++i){
        for(j=find(S2[i].l);j<=S2[i].r;j=r[j]){
            if(vv[j]==0x3f3f3f3f)vv[j]=S2[i].k;
            r[j]=find(j+1);
        }
    }
      
    for(i=1;i<=l;++i)printf("%d\n",min(l,min(v[i]+i,vv[i])));
      
    return 0;
}

Tags: 后缀自动机并查集
Posted in BZOJ | 0 Comments

BZOJ2780:[Spoj]8093 Sevenk Love Oimaster 后缀自动机+离线+dfs序+树状数组

10 年前

思路:

首先建立多串后缀自动机(别问我怎么建的)

然后对于每个询问串在自动机上走,记录下走到的节点.那么在几个串中出现等价于逆序后缀树的子树中有几个原串的后缀.

转化为dfs序之后,这等价于每次询问一段区间有几种不同的数.

经典模型,离线+树状数组水.

(我TTMD坑了QoQ)

100

101

102

103

104

105

106

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
    
int n,m;
struct Graph{
    int head[200010],next[200010],end[200010],ind;
    inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
}w,g;
    
int len[200010],deg[200010],pa[200010],cnt,root,last;
map<int,int>tranc[200010];
int newnode(int l){
    len[++cnt]=l;return cnt;
}
    
char s[360010];
    
int in[200010],out[200010],seq[200010],tclock;
inline void dfs(int x){
    in[x]=++tclock;seq[tclock]=x;
    for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
    out[x]=tclock;
}
    
int pre[10010];
struct Ask{
    int lab,l,r;
    Ask(){}
    Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
    bool operator<(const Ask&B)const{return r<B.r;}
}S[60010];
    
int A[200010];
inline void mdf(int x,int add){
    for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
    int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
    
int lastins[10010];
int ans[60010];
    
void get(int x){for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");}
    
int main(){
    scanf("%d%d",&n,&m);
    register int i,j,k;int l,y,p,np,q,nq,rep,tmp;
    for(root=newnode(0),i=1;i<=n;++i){
        scanf("%s",s);l=strlen(s);
        for(last=root,j=0;j<l;++j){
            if((p=tranc[last][y=s[j]])!=0){
                if(len[p]==len[last]+1)last=p;
                else{
                    rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
                    tranc[rep]=tranc[p];
                    for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
                    last=rep;
                }
            }
            else{
                np=newnode(len[last]+1);
                for(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[np]=pa[q]=nq;
                        tranc[nq]=tranc[q];
                        for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
                    }
                }last=np;
            }
            w.addedge(last,i);
        }
    }
    for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
    dfs(1);
        
    bool find;
    for(i=1;i<=m;++i){
        scanf("%s",s);l=strlen(s);find=1;
        for(p=root,j=0;j<l;++j){
            y=s[j];if(!tranc[p][y]){find=0;break;}p=tranc[p][y];
        }
        if(find)S[i]=Ask(i,in[p],out[p]);else S[i]=Ask(i,-1,-1);
    }sort(S+1,S+m+1);
        
    int noww;k=1;while(k<=m&&S[k].l==-1)++k;
    for(i=1;i<=cnt;++i){
        for(j=w.head[seq[i]];j;j=w.next[j]){
            noww=w.end[j];
            mdf(i,1);if(lastins[noww])mdf(lastins[noww],-1);lastins[noww]=i;
        }
        for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
    }
        
    for(i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}

Tags: 后缀自动机离线处理树状数组 dfs序
Posted in BZOJ | 2 Comments

[开新坑]对于后缀自动机的一些理解

10 年前

感觉单纯地从"后缀自动机"的角度来入手并不是非常合理.因为我们懂得很多"后缀自动机"的性质,但却并不清楚"后缀自动机"在本质上是什么.

让我们从后缀树说起.

Tags: 后缀树后缀自动机
Posted in Something | 6 Comments

Codechef 12.12 DIFTRIP Trie树+后缀自动机+STL

Codechef 12.4 TSUBSTR 后缀自动机+Trie

BZOJ3998: [TJOI2015]弦论后缀自动机

BZOJ3413:匹配后缀自动机

BZOJ2882:工艺 STL+后缀自动机

BZOJ3277:串后缀自动机+离线处理+树状数组(&&BZOJ3473)

BZOJ1396:识别子串后缀自动机+并查集(&&BZOJ2865)

BZOJ2780:[Spoj]8093 Sevenk Love Oimaster 后缀自动机+离线+dfs序+树状数组

[开新坑]对于后缀自动机的一些理解

search

lastest comments

friend links

visitor counter

search

tags

lastest comments

friend links

visitor counter