首页 > 代码库 > BZOJ 2882 工艺 后缀自动机
BZOJ 2882 工艺 后缀自动机
题目大意:最小表示法模板题
不会最小表示法,拿后缀自动机水了一发~~
一开始还写挂了MLE…… 权当练习一下SAM的熟练度了0.0
#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 300300 using namespace std; int n,a[M]; namespace Suffix_Automaton{ struct SAM{ map<int,SAM*> son; SAM *parent; int dpt; void* operator new (size_t,int _); }*root=new (0) SAM,*last=root,mempool[M<<2],*C=mempool; void* SAM :: operator new (size_t,int _) { C->dpt=_; return C++; } void Extend(int x) { SAM *p=last; SAM *np=new (p->dpt+1) SAM; for(;p&&!p->son[x];p=p->parent) p->son[x]=np; if(!p) np->parent=root; else { SAM *q=p->son[x]; if(p->dpt+1==q->dpt) np->parent=q; else { SAM *nq=new (0) SAM; *nq=*q;nq->dpt=p->dpt+1; q->parent=nq;np->parent=nq; for(;p&&p->son[x]==q;p=p->parent) p->son[x]=nq; } } last=np; } void Get_Min(int len) { SAM *p=root; while(len--) { map<int,SAM*>::iterator it=p->son.begin(); printf("%d%c",it->first,len?' ':'\n'); p=it->second; } } } int main() { int i,x; cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]),Suffix_Automaton::Extend(a[i]); for(i=1;i<n;i++) Suffix_Automaton::Extend(a[i]); Suffix_Automaton::Get_Min(n); return 0; }
BZOJ 2882 工艺 后缀自动机
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。