一直记不住的 马拉车 板子. 前几天校内选拔赛还不会写, 惨遭吊打.

综述

对于一个长度为 $n$ 的字符串, Manacher 可以在 $O(n)$ 的时间内对每个位置 $i$ 计算一个类似于最长回文半径的东西.

具体而言, Manacher 在扫描每个位置的时候, 维护一个右端点最靠右的回文串的左右端点, 并借助于这个回文串来计算需要的信息.

阅读全文

谨以此题纪念自己颓废的, 什么都不会的高一 (bushi

• 题目链接: https://www.luogu.com.cn/problem/P5284

SAM 优化建图 + 拓扑排序求最长路.

写这道题啊, 只是感到自己的高一很可笑吧, 连题意都不大能读清, 正解的算法听都没有听过, 输出样例就弃疗离场.

阅读全文

• 题目链接: https://www.luogu.com.cn/problem/P4762

一道回文自动机 + DP 的题, 感觉能启发思路以及学习到一些技巧, 故记之.

阅读全文

• 题目链接: https://www.luogu.com.cn/problem/P2336

一道后缀数组的题, 毒瘤了我大半个晚上, 故写题解以纪念.

阅读全文