[[字符串]]

前言

链接

今日是字符串专题，我觉得还挺有趣的。

不过字符串难的题目也确实很难。

没有看后缀自动机，等 CSP 考完吧。

阿狸的打字机

有些题还是很有趣的，有一道离线树状数组的题我硬生生写了个主席树，不过看题解发现离线没写好会被 hack，所以在线主席树 yyds！

重点

KMP，自动 AC 机 AC 自动机，字符串 hash，另外可能还有 KMP 自动机。

字符串 hash 要注意，不然容易被 hack，或者被生日悖论搞。

一般要用双 hash 或者是级别的质数来 hash，虽然我没有明白为什么一定要是质数。

P.S. AC 自动机我已经很熟悉啦，要是后缀自动机和后缀数组也能像这样就好哩。

后记

今天练习赛第十题基本上是一遍过，错误是因为不知道主席树要开多大空间，在这里记录一下，，是询问次数，其中前面的开四倍空间，后面一坨单点修改一倍，区间两倍。（如果错了欢迎指正，话说没有评论区怎么办啊）