一个 \(A\) 合法的充要条件为：
- \(A\) 为 \(S_{1 \sim i}\) 的一个 border；
- \(A\) 在 \(S_{1 \sim i}\) 中不重叠地出现 \(\ge k\) 次。
建出失配树后，发现合法的 \(A\) 在树上组成一条某个点 \(u\) 到根的链，且 \(u\) 为 \(i\) 的祖先。因此我们若知道 \(u\)，答案就是 \(dep_u\)。
考虑倍增求出 \(u\)。相当于要 check 这样一个问题：
- \(S_{1 \sim u}\) 的第 \(k\) 次不重叠出现位置是否 \(\le i\)。
考虑预处理出每个前缀 \(S_{1 \sim u}\) 对应的串在整个串中的不重叠出现位置。相当于每次找到一个位置后面第一个后缀，使得它与整个串的 LCP 长度 \(\ge u\)，然后跳到它。跳的步数最多是 \(\sum\limits_{i = 1}^n \frac{n}{i} = O(n \log n)\) 所以可以暴力跳。
一个后缀与整个串的 LCP 长度可以想到 Z 函数。用并查集维护链表的 trick，从小到大枚举 \(u\)，处理完 \(u\) 后把 \(z_p = u\) 的所有位置 \(p\) 删了，使得处理到 \(u\) 时，并查集中 \(z_p \ge u\) 的位置为代表元。这样即可 \(O(\alpha(n))\) 求出一个位置后面第一个 \(p\) 使得 \(z_p \ge u\) 的 \(p\)。
注意特判 \(k = 1\)。
总时间复杂度 \(O(q \log n + n \alpha(n) \log n)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int logn = 20;
int n, m, fail[maxn], dep[maxn], z[maxn], st[logn][maxn], f[logn][maxn], fa[maxn];
char s[maxn];
vector<int> vc[maxn], cv[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void solve() {
scanf("%d%s%d", &n, s + 1, &m);
for (int i = 2, j = 0; i <= n; ++i) {
while (j && s[i] != s[j + 1]) {
j = fail[j];
}
j += (s[i] == s[j + 1]);
fail[i] = j;
}
for (int i = 1; i <= n; ++i) {
f[0][i] = fail[i];
dep[i] = dep[fail[i]] + 1;
}
for (int j = 1; j <= 19; ++j) {
for (int i = 1; i <= n; ++i) {
f[j][i] = f[j - 1][f[j - 1][i]];
}
}
z[1] = n;
for (int i = 2, l = 0, r = 0; i <= n; ++i) {
if (i <= r) {
z[i] = min(z[i - l + 1], r - i + 1);
}
while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
for (int i = 1; i <= n; ++i) {
cv[z[i]].pb(i);
fa[i] = (z[i] ? i : i + 1);
}
fa[n + 1] = n + 1;
for (int i = 1; i <= n; ++i) {
vc[i].pb(i);
int p = i;
while (p + i <= n) {
int q = find(p + 1);
if (q == n + 1) {
break;
}
p = q + i - 1;
vc[i].pb(p);
}
for (int j : cv[i]) {
fa[j] = j + 1;
}
}
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
if (y == 1) {
puts("1");
continue;
}
int t = x;
for (int i = 19; ~i; --i) {
if (f[i][x] && ((int)vc[f[i][x]].size() < y || vc[f[i][x]][y - 1] > t)) {
x = f[i][x];
}
}
x = f[0][x];
printf("%d\n", dep[x]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}