[SDOI2016]生成魔咒-白红宇

[SDOI2016]生成魔咒

阅读量：6440 次

发布时间：2019-06-23

本文共 2128 字，大约阅读时间需要 7 分钟。

OJ题号：

　　BZOJ4516

题目大意：

　　按顺序在一个序列的末尾插入数字，每次求出插入后能得到的本质不同的子串个数。

思路：

　　每次在SAM后加入这个数字，每次新出现的本质不同的子串个数就等于new_p->len-new_p->link->len。

　　由于数字范围比较大，可以考虑离散化或者map。

　　事实上也可以用hash，不过实践证明会比map还慢很多，内存也浪费很多。

　　另外需要注意开long long。

1 #include 2 #include
      
        3 #include
       
         4 inline int getint() { 5     char ch; 6     while(!isdigit(ch=getchar())); 7     int x=ch^'0'; 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9     return x;10 }11 class SuffixAutomaton {12     private:13         struct State {14             State *link;15             std::map
        
          go;16             int len;17             State(const int l) {18                 link=NULL;19                 len=l;20             }21         };22         State *root,*last;23         long long ans;24         void extend(const int w) {25             State *p=last,*new_p=new State(last->len+1);26             while(p!=NULL&&!p->go.count(w)) {27                 p->go[w]=new_p;28                 p=p->link;29             }30             if(p==NULL) {31                 new_p->link=root;32             } else {33                 State *q=p->go[w];34                 if(q->len==p->len+1) {35                     new_p->link=q; 36                 } else {37                     State *new_q=new State(p->len+1);38                     new_q->go=q->go;39                     new_q->link=q->link;40                     q->link=new_p->link=new_q;41                     while(p!=NULL&&p->go[w]==q) {42                         p->go[w]=new_q;43                         p=p->link;44                     }45                 }46             }47             last=new_p;48             ans+=new_p->len-new_p->link->len;49         }50     public:51         SuffixAutomaton() {52             root=last=new State(0);53         }54         long long query(const int w) {55             extend(w);56             return ans;57         }58 };59 SuffixAutomaton sam;60 int main() {61     for(int n=getint();n;n--) printf("%lld\n",sam.query(getint()));62     return 0;63 }

附hash_map和map的比较：