2023/1/8

周报

大主题：

字符串&动态规划&数论

本周总结：

本周主要是继续对字符串（后缀自动机SAM、广义后缀自动机GSAM、回文树/回文自动机PAM、序列自动机SUBM）的学习。

1. GSAM学习笔记：C.C--/一些算法和数据结构/字符串/广义后缀自动机GSAM at master · JoshuaZhengsurp/C.C-- (github.com)

2. PAM学习笔记：C.C--/一些算法和数据结构/字符串/回文树(回文自动机) at master · JoshuaZhengsurp/C.C-- (github.com)

3. SUBM学习笔记：C.C--/一些算法和数据结构/字符串/序列自动机sub_AM at master · JoshuaZhengsurp/C.C-- (github.com)

GSAM算法对SAM运用的扩展，在字典树或其他树形结构的基础上构建一个后缀自动机，相交于SAM，更能胜任对多串问题的有效解决，不够在构造上，有时要比较彻底的魔改，应用上和SAM类似。

而PAM这是处理回文串问题的一大利器，对于部分回文串相关的难题来说，使用PAM比单纯使用manacher算法的思维量其实要少很多，例如这题最长双回文串。在构造上也要比SAM好构造，复杂度为（O\((n\sum{const})\))。

第三个SUBM，相较于其他自动机来说，这是最为简单的一个，常用来处理子序列问题，构造算法采用了动态规划的思想（而在求公共子序列时也需要dp）。

本周的状态要比上周差不少，实在拉跨。下周打算动态规划复健一波，以及二叉树的学习（treap，splay...）

题目完成情况：

题目位置：我与字符串的那些事 - Virtual Judge (vjudge.net)

（对应题号）题解代码：C.C--/excising/diu_diu/String at master · JoshuaZhengsurp/C.C-- (github.com)

题目：