标准模板

将字符串映射到数,以便实现 的字符串判重。

我们自己取一个滴数 , 膜数

那么

就是整个字符串的哈希值。

为了避免哈希冲突(及两个不同的字符串哈希值相同)的情况,我们一般将 选为质数。

如果只需判重,可以同时计算几个不同底数、模数的哈希值,防止哈希碰撞。

区间的哈希

那么

例题

#10035. 「一本通 2.1 练习 1」Power Strings

求字符串的最小循环节。

字符串以 为循环节等价于

画图可知显然。

#10038. 「一本通 2.1 练习 4」A Horrible Poem

给定只含小写字母的字符串,求区间的最小循环节。

如果这个区间的最大循环节是 ,

那么 ,且 一定整除区间内的各个字母出现次数

每次询问区间内各字母个数的最大公约数。

能过

#2427. 「POI2010」珍珠项链 Beads

正解就是暴力。记住调和级数

小细节:此题需要记录正着反着两种哈希值。

做法

利用线性筛求出每个数的最小质因子。

如果 是循环节,那么显然 )也是循环节。

从大到小枚举因子即可。

用于获取 的所有质因子,试着去除 , 就可以枚举到所有质因子。

(实际上没有枚举所有,但是由于上述性质,可以得到答案所需的那个最小因子。)