标签: 后缀数组(SA)

  • MOCK NOIP 20221117 日志

    T1 的 Hack 数据提醒我,尽管时间复杂度没有变化,但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

    T2 没有认真读题,忽略了“恰执行一次”的要求。

    T3 里面没有使用自己熟悉的存边方式,时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

    简单题解

    A – 跳棋

    从 $(x,y)$ 跨步跳能够跳到 $(x\pm 2,y),(x,y\pm 2)$,以及 $(x+k,y+k),k=\pm 2$。可以发现 $x,y$ 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块,在这些连通块上 BFS 即可。

    若采用 std::map 存储,时间复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)$。需要采纳“避免遍历不存在的连通块”之类的优化。 (更多…)

  • 洛谷题库 P4770 [NOI2018] 你的名字 题解与思路重现

    洛谷题库 P4770 [NOI2018] 你的名字

    本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。

    也就是说,大体思路只花费一小时不到,去掉一个 $\log$ 却耗了我一天多……

    “双指针”扫描求串 $T$ 的每个前缀在 $S$ 中匹配的最长子串

    在任何时刻,SAM 的状态转移函数会将某字符串引向串 $S$ 中的等价 $\mathrm{endpos}$ 状态。根据 $\mathrm{endpos}$ 和 parent tree 的性质,我们可以对前缀 $T[1\cdots k], k \in \{1, 2,\cdots, |T|\}$ 依次求出其最长的作为 $S$ 的子串出现的后缀。 (更多…)