A Horrible Poem-字符串哈希+线性筛 题目描述 题解 首先明确几个性质 1，循环节的长度必为该区间 S [ a . . . b ] S[a...b] S[a...b]长度的约数—显而易见 2，当 S [ a . . . b − l e n ] = = S [ a + l e n . . . b ] S[a...b-len]==S[a+len...b] S[a...b−len

思路 线段树 区间更新 模板题 注意数据范围 AC代码 #include <cstdio>#include <cstring>#include <ctype.h>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <deque>#include <vector>#i

题目传送门 题目大意： 有一个长度为 n n n的字符串，每次询问一个字串的最短循环节。 题解 最最暴力的做法：枚举长度 l e n len len，每次将该长度的字串与原串暴力匹配一遍。 然后考虑优化： 1. 显然 l e n len len 一定是 n n n 的因数，于是枚举 l e n len len 的时候只需要枚举 n n n 的因数即可。 2. 匹配可以用哈

一.题目链接： HYSBZ-2795 二.题目大意： 给一个长度为 n 的字符串，q 次询问，每次问 s[l...r] 的最小循环节. 三.分析： 技巧一：字符串 s[l, r] 具有循环节 k 等价于 s[l, r - k] == s[l + k, r]. 技巧二：线性筛中预处理出每个数的最小质因子，可  进行质因数分解.  技巧三：字符串的最小循环节可通过对字符串长