循环字符串
题目描述
给定长度为 $n$ 的字符串，有 $m$ 次操作，每次操作都是以下三种之一：
一：$0,l,r,c$; 把 $[l,r]$ 的每个位置的字符都替换为字母 $c$，保证字符串和 $c$ 都是小写字母。
二：$1,l,r$; 询问子串 $s_l s_{l+1} \ldots s_{r−1} s_r$ 的最小循环节长度。
三：$2,l,r$; 询问子串 $s_r s_{r−1} \ldots s_{l+1} s_l$ 的最小循环节长度。
循环节：假设字符串 $s_1 s_2 s_3 \ldots s_n$ 的循环节为字符串 $T$：$t_1 t_2 \ldots t_x$，那么将整数个字符串 $T(t_1 t_2 \ldots t_x)$ 首尾相连就能得到 $s_1 s_2 \ldots s_n$ 比如 $acacacac$ 的循环节可以是 $ac$（$ac+ac+ac+ac=acacacac$），也可以是 $acac$（$acac+acac=acacacac$）。
输入描述:
输入格式：
第一行输入两个整数 $n(1 \leq n \leq 2 \cdot 10^5)$，$m(1 \leq m \leq 10^6)$。
第二行输出长度为 $n$ 且只包含小写字母的字符串 $s$ 接下来 $m$ 行每行一个操作，格式和上述一致，保证 $r \geq l$。
输出描述:
对于每次操作 2 和 3，输出最小循环节长度。
示例1
输入
8 6
aaabcabc
1 1 3
2 3 8
0 2 4 c
1 4 5
0 3 6 b
2 2 7输出
1
3
1
6说明
四次询问的最小循环节分别为：a, abc, c, cbbbbbb
示例2
输入
18 12
acacqcjjznggzoalyy
2 1 4
1 1 6
0 5 5 a
2 1 6
0 9 9 j
0 10 10 g
2 7 12
2 6 10
0 4 9 z
2 9 13
1 3 11
1 6 6输出
2
6
2
6
5
5
9
1
解题思路
首先两个询问操作是等价的，因为循环节 $k$ 满足 $k \mid (r-l+1)$，因此翻转后的字符串的循环节依然是 $k$，相当于把原本的循环节翻转然后拼接。因此接下来只讨论第一种查询。
对于每个查询，显然可以枚举 $r-l+1$ 的每个因子 $k$ 进行判断，有结论，如果一个字符串是 $k$ 循环节则充分必要条件是 $s[l+k, r] = s[l, r-k]$。而快速判断两个字符串是否相同可以用字符串哈希，由于涉及到修改操作，因此还需要用线段树来动态维护区间的字符串哈希，其中两个字符串 $s_l, \, s_r$ 合并（对应 pushup 操作）得到的哈希值为 $h(s_l + s_r) = h(s_l) \times P^{|s_2|} + h(s_2)$。
上述做法的时间复杂度为 $O(q \sqrt{n} \log{n})$，虽然时限给了 $7$ 秒但常数太大是过不了的。可以想一下，有必要枚举 $r-l+1$ 的所有因子吗？首先 $r-l+1$ 必然是一个循环节，假设最小的循环节是 $k$，$\frac{r-l+1}{k} = P_{1}^{\alpha_{1}} \cdots P_{m}^{\alpha_{m}}$，那么 $k \times \prod\limits_{i=1}^{m}{P_{i}^{\beta_{i}}}, \, (0 \leq \beta_{i} \leq \alpha_{i})$ 也必然是一个循环节。为此我们可以枚举 $r-l+1$ 的所有质因子，从 $r-l+1$ 开始不断试除，最后得到最小的循环节 $k$。一个数 $n$ 最多有 $O(\log{n})$ 个质因子。
AC 代码如下，时间复杂度为 $O(q \log^2{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 2e5 + 5, P = 13331;
char str[N];
ULL p[N], s[N];
int primes[N], minp[N], cnt;
bool vis[N];
struct Node {
int l, r;
ULL h, add;
}tr[N * 4];
void pushup(int u) {
tr[u].h = tr[u << 1].h * p[tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1] + tr[u << 1 | 1].h;
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) {
tr[u].h = str[l];
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void pushdown(int u) {
if (tr[u].add) {
tr[u << 1].h = s[tr[u << 1].r - tr[u << 1].l] * tr[u].add;
tr[u << 1].add = tr[u].add;
tr[u << 1 | 1].h = s[tr[u << 1 | 1].r - tr[u << 1 | 1].l] * tr[u].add;
tr[u << 1 | 1].add = tr[u].add;
tr[u].add = 0;
}
}
void modify(int u, int l, int r, char c) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].h = s[tr[u].r - tr[u].l] * c;
tr[u].add = c;
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, c);
if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
pushup(u);
}
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
if (l >= mid + 1) return query(u << 1 | 1, l, r);
Node t1 = query(u << 1, l, r), t2 = query(u << 1 | 1, l, r);
return {t1.l, t2.r, t1.h * p[t2.r - t2.l + 1] + t2.h};
}
void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes[cnt++] = i, minp[i] = i;
for (int j = 0; primes[j] * i <= n; j++) {
vis[primes[j] * i] = true;
minp[primes[j] * i] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m >> str + 1;
p[0] = s[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
s[i] = s[i - 1] + p[i];
}
build(1, 1, n);
get_prime(n);
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (!op) {
char c;
cin >> c;
modify(1, l, r, c);
}
else {
int len = r - l + 1, ret = len;
while (len > 1) {
int p = minp[len];
while (minp[len] == p) {
if (query(1, l + ret / p, r).h == query(1, l, r - ret / p).h) ret /= p;
len /= p;
}
}
cout << ret << '\n';
}
}
return 0;
}
参考资料
代码查看：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70749770
河南萌新联赛2024第（四）场：河南理工大学题解：https://ac.nowcoder.com/discuss/1344333
标签：ac,int,len,leq,循环,字符串 From： https://www.cnblogs.com/onlyblues/p/18348706