popoqqq 2023-04-19 00:54:00 博主文章分类：BZOJ ©著作权

文章标签 BZOJ BZOJ3238 后缀自动机 #include 后缀树 文章分类 HarmonyOS 后端开发

题目大意：给定一个字符串，求Σ[1parent) p->son[x]=np; if(!p) np->parent=root; else { SAM *q=p->son[x]; if(p->max_dpt+1==q->max_dpt) np->parent=q; else { SAM *nq=new SAM(p->max_dpt+1); nq->son=q->son; nq->parent=q->parent; q->parent=nq;np->parent=nq; for(;p&&p->son[x]==q;p=p->parent) p->son[x]=nq; } } last=np; np->right++; } } int n; long long ans; char s[M]; void DFS(Suffix_Automaton::SAM *p) { using namespace Suffix_Automaton; map::iterator it; if(p->parent) p->parent->tree_son.push_back(p); p->mark=1; for(it=p->son.begin();it!=p->son.end();it++) if( !(it->second)->mark ) DFS(it->second); } void Tree_DP(Suffix_Automaton::SAM *p) { using namespace Suffix_Automaton; vector::iterator it; for(it=p->tree_son.begin();it!=p->tree_son.end();it++) { Tree_DP(*it); ans-=(long long)p->max_dpt*p->right*(*it)->rightright; } } int main() { using namespace Suffix_Automaton; int i; scanf("%s",s+1);n=strlen(s+1); for(i=n;i;i--) Extend(s[i]-'a'); ans=(long long)(n-1)*n*(n+1)/2; DFS(root);Tree_DP(root); cout 赞 收藏 评论 分享 举报

上一篇：BZOJ 2286 SDOI2011 消耗战 倍增LCA+单调栈

下一篇：BZOJ 2400 Optimal Marks 最小割