【bzoj2795】[Poi2012]A Horrible Poem Hash+分解质因数
HASH 分解 质因数
2023-09-11 14:22:40 时间
题目描述
给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。
输入
第一行一个正整数n (n<=500,000),表示S的长度。
第二行n个小写英文字母,表示字符串S。
第三行一个正整数q (q<=2,000,000),表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n),表示询问字符串S[a..b]的最短循环节长度。
输出
依次输出q行正整数,第i行的正整数对应第i个询问的答案。
样例输入
8
aaabcabc
3
1 3
3 8
4 8
样例输出
1
3
5
题解
Hash+分解质因数
考虑如何求出一个字符串的最短循环节?使用KMP求出next数组,n-next[n]即为最短循环节。
那么考虑本题,判断一个长度是否为循环节,只需要判断前后字符串是否相等即可,可以使用Hash解决。
因为循环节长度一定是字符串长度的约数,由于一个数的约数最多只有$2\sqrt n$个,因此可以枚举约数然后判断,时间复杂度$O(q\sqrt n)$
考虑优化这个过程:如果$i$是循环节,那么$ki\ (ki|len)$也一定是循环节。所以我们可以对于串长的每个质因子,求出它在最短循环节中的指数次数。具体实现即对于现有循环节,判断除以质因子后是否还是循环节,如果是则除,不是则不变。
而分解质因数是可以通过线性筛做到线性预处理$O(\log n)$查询的,故总时间复杂度为$O(n+q\log n)$。
#include <cstdio> #include <cstring> #include <algorithm> #define N 500010 using namespace std; typedef unsigned long long ull; ull base[N] , hash[N]; int lp[N] , prime[N] , tot , np[N]; char str[N]; bool judge(int l , int r , int len) { return hash[l + len - 1] - hash[l - 1] * base[len] == hash[r] - hash[r - len] * base[len]; } int main() { int n , i , j , m , l , r , v , now; scanf("%d%s%d" , &n , str + 1 , &m); for(i = 2 ; i <= n ; i ++ ) { if(!np[i]) lp[i] = i , prime[++tot] = i; for(j = 1 ; j <= tot && i * prime[j] <= n ; j ++ ) { np[i * prime[j]] = 1 , lp[i * prime[j]] = prime[j]; if(i % prime[j] == 0) break; } } base[0] = 1; for(i = 1 ; i <= n ; i ++ ) base[i] = base[i - 1] * 2333 , hash[i] = hash[i - 1] * 2333 + str[i]; while(m -- ) { scanf("%d%d" , &l , &r) , now = v = r - l + 1; while(v != 1) { if(judge(l , r , r - l + 1 - now / lp[v])) now /= lp[v]; v /= lp[v]; } printf("%d\n" , now); } return 0; }
相关文章
- 消息摘要、哈希(hash)、加盐
- 如何设置redis中hash的field的expire ?
- Nginx upstream_ip_hash_module 基于Hash算法实现负载均衡
- Redis开发:hash存储自定义Java对象及value的序列化器设置
- iOS 方法查找 cache查找 hash查找
- 【华为云技术分享】【技术总结】从Hash索引到LSM树
- 【架构实践】一致性Hash算法原理图文详解 & 使用 golang 实现
- 一致性hash(整理版)
- 内网渗透(四十八)之域控安全和跨域攻击-多种方式在线读取ntds.dit文件中的hash值
- Hash Collision DoS 问题
- Javascript混淆与解混淆的那些事儿——JS混淆归结为三类,分别是 eval类型,hash类型,压缩类型
- cassandra框架模型之一——Colum排序,分区策略 Token,Partitioner bloom-filter,HASH
- 【redis源码学习】紧凑列表 listpack,t_hash的御用底层结构