题目链接

洛谷

CF

题意简述

给你一个字符串，求有多少对相交的回文子串。（包含算作相交，自交不算）

字符串长度小于等于 $2\times 10^6$。

题目链接

洛谷

CF

题意简述

给你一个字符串，分别求出每个长度的既是其前缀又是其后缀的串出现的次数。

字符串长度小于等于 $10^5$。

题目链接

洛谷

CF contest

CF problemset

题意简述

给你两个字符串 $S$ 和 $T$，你需要在 $S$ 中取若干个（至少一个）不相交的子串，使得每个子串都包含 $T$，求方案数模 $10^9+7$。

字符串长度小于等于 $10^5$。

题目链接

洛谷

darkbzoj

题意简述

给一个长为 $m$ 的字符串，字符集 $0$ ~ $9$，求长为 $n$ 的字符串中不含给定字符串作为子串的字符串有多少个，对 $k$ 取模。

$n\le10^9$，$m\le20$，$k\le1000$。

题目链接

洛谷

darkbzoj

题意简述

初始一个空串，三种操作：

1. 添加一个字符。
2. 删除一个字符。
3. 打印当前字符串、

多组询问，每次问第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了几次。

操作数和询问数都不超过 $10^5$。

AC 自动机其实我去年就学过了，但当时大约只是会敲模板而已..现在几乎全忘光了。于是复习一下，顺便（较为本质地）讲解一下。

题目链接

洛谷

题意简述

给你一个 DAG，每个点有个值 $k_i$。

第一问：求一个拓扑排序，使每个点出现的位置不超过 $k_i$。

第二问：在满足第一问的拓扑排序中，求每个点分别的最早出现位置。

口中喊着「僕勝つから。ぜったい、勝て来るから。」的你，真的付出了桐山般的努力吗？

最近发现 OI Wiki 的“树分块”是空的，本来想凭着之前写的莫队教程水一水，结果被告知已经有人写过树上莫队了..于是就得详细介绍一下树分块除了树上莫队以外的应用..然而我除了糖果公园只做过一道树分块..（结果最后并没有找到这道题以外的其它题..）

随便找了点省选前需要复习的知识点相关的题目..