第3题-塔子哥构造字符串 - Problem Detail - CodeFun2000

1000ms

Difficulty: 6

算法与标签>动态规划

会员或题库专享

请先，开通会员，可解锁完整内容。

开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库，可解锁完整内容。

开通会员

字典树复杂度 $O(N^2S)$ $S$ 为字符集大小，也可以改到 $O(N^2logS)$ 。

注意到在下标 $i$ 往右移动的时候，字典树内索引是否合法具有单调性，考虑对树中每一个节点维护一个指针 $curidx[u]$ 来把复杂度均摊到 $O(N^2S)$

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")