admin 管理员组文章数量: 887021
OKR
O K R − A H o r r i b l e P o e m OKR-A\ Horrible\ Poem OKR−A Horrible Poem
题目链接：luogu P3538
题目大意
给出一个由小写英文字母组成的字符串 S S S，再给出 q q q个询问，要求回答 S S S某个子串的最短循环节。
如果字符串 B B B是字符串 A A A的循环节，那么 A A A可以由 B B B 重复若干次得到。
输入
第一行一个正整数 n ( n ≤ 500 000 ) n(n≤500\ 000) n(n≤500 000)，表示 S S S的长度。
第二行 n n n个小写英文字母，表示字符串 S S S。
第三行一个正整数 q ( q ≤ 2 000 000 ) q(q≤2\ 000\ 000) q(q≤2 000 000)，表示询问次数。
下面 q q q行每行两个正整数 a , b ( 1 ≤ a ≤ b ≤ n ) a,b(1≤a≤b≤n) a,b(1≤a≤b≤n),表示询问字符串 S [ a … b ] S[a…b] S[a…b]的最短循环节长度。
输出
给出一个由小写英文字母组成的字符串 S S S，再给出 q q q个询问，要求回答 S S S某个子串的最短循环节。
如果字符串 B B B是字符串 A A A的循环节，那么 A A A可以由 B B B重复若干次得到。
样例输入
8
aaabcabc
3
1 3
3 8
4 8
样例输出
1
3
5
思路
这道题用 h a s h hash hash来做。
因为要求字符串的最短循环节，就要判断字符串是否相同，自然就会用到 h a s h hash hash。
既然知道了怎么判断两个字符串是否相同，就要判断某个小字符串是否是某个字符串的循环节。当然，我们不能直接一个一个地枚举那个字符串里面的小字符串（因为会超时），那怎么办呢？
有一种方法：设 a [ i ] [ j ] a[i][j] a[i][j]为 a a a字符串从第 i i i为到第 j j j位，如果我们要判断 b [ k ] [ l ] b[k][l] b[k][l]这个小字符串（长度为 l e n len len）是它的循环节的话，我们只要判断 a [ i ] [ j − l e n ] = = a [ i + l e n ] [ j ] a[i][j−len]==a[i+len][j] a[i][j−len]==a[i+len][j]。原因的话自己模拟看看就知道了。
在枚举循环节的长度的时候，我们不一定要枚举全部的长度，我们只要在循环节循环次数是字符串的长度的约数的情况下才需要枚举这个长度。
代码
#include<cstdio>
#define rr register
#define min(x, y) (x) < (y) ? (x) : (y) using namespace std;int n, m, x, y, p = 131, P[500001], hash[500001], b[500001][27], ans;
char a[500001];int geth(int l, int r) {//得到字符串的hash值return hash[r] - hash[l - 1] * P[r - l + 1];
}void find (int length) {//如果是判断出是循环节的话就判断是否比当前最优解还要优if (geth(x + length, y) == geth(x, y - length)) ans = min(ans, length);
}int gcd(int l, int r) {//求gcdif (r == 0) return l;return gcd(r, l % r);
}int read() {//快读int an = 0;char c = getchar();while (c > '9' || c < '0') c = getchar();while (c <= '9' && c >= '0') {an = an * 10 + c - 48;c = getchar();}return an;
}int main() {n = read();//读入scanf("%s", a + 1);//读入P[0] = 1;//初始化for (rr int i = 1; i <= n; i++)P[i] = P[i - 1] * p;//预处理hash的进制for (rr int i = 1; i <= n; i++)hash[i] = hash[i - 1] * p + a[i] - 'a' + 1; //转换hash并记录前缀和for (rr int i = 1; i <= n; i++) {for (int j = 1; j <= 26; j++)b[i][j] = b[i - 1][j];//前缀和出单词出现的位置与频率b[i][a[i] - 'a' + 1]++;//记录单词的出现}scanf("%d", &m);//读入for (rr int i = 1; i <= m; i++) {x = read();//读入y = read();//读入int len = y - x + 1;//求出长度ans = 2147483647;//初始化for (int i = 1; i <= 26; i++)len = gcd(len, b[y][i] - b[x - 1][i]);//对小序列中每个字母出现次数取gcdfor (int i = 1; i * i <= len; i++) {//枚举循环次数if (len % i) continue;//循环次数须为序列长度的约数find((y - x + 1) / i);//计算循环次数为i次的结果，更新答案find((y - x + 1) / (len / i));//计算循环次数为len/i次的结果，更新答案}printf("%d\n", ans);//输出}return 0;
}
本文标签： OKR
版权声明：本文标题：OKR 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1725706306h875760.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论