BZOJ 3277 串 题解
Statement
给 \(n\) 个串，问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。
Solution 1
对于每个后缀，二分他最右的满足条件的前缀，这就是他贡献多少次。
设二分的 \(x\)，可以二分找出 height 上左边、右边第一个 \(<\) 他的位置
同样预处理对于所有 \(l\)，最左的 \(r\) 满足 \([l..r]\) 中出现了至少 \(k\) 个串的后缀。
找到管辖区间 \([l..r]\) 后就可以 \(O(1)\) 判了。
\(O(n\log^2 n)\)
Solution 2
考虑优化
考虑到原串中若后缀 \(i-1\) 有 \(x\) 个前缀是至少 \(k\) 个串的子串，那么后缀 \(i\) 有至少 \(x-1\) 个前缀是至少 \(k\) 个串的子串
按这样的方式算，是 \(O(n\log n)\)
Solution 3
建广义 SAM
设 \(p(u)\) 为 \(u\) 来自哪个串，\(u\) 的出现次数就是他的子树内 \(p\) 的种类数，这就是 HH 的项链
然后对于每个串的答案，在 SAM 上走一遍，每次若出现次数 \(<k\) 就一直跳 \(\text{link}\)，直到出现次数 \(\ge k\) 然后给答案加上 \(\text{len}(u)\).
\(O(n\log n)\)
Code 1
log^2
// log^2
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10, LN = 20;
string T, s[N];
int n, m = 27, p, t, k, sa[N], rk[N], se[N], cnt[N], height[N], belongs[N], suffixlength[N];
void Rsort() {
rep(i, 1, m) cnt[i] = 0;
rep(i, 1, n) ++cnt[rk[i]];
rep(i, 1, m) cnt[i] += cnt[i - 1];
reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
void SA() {
if (n == 1) return (void)(sa[1] = rk[1] = 1);
rep(i, 1, n) rk[i] = ('a' <= T[i - 1] && T[i - 1] <= 'z') ? (T[i - 1] - 'a' + 1) : 27, se[i] = i;
Rsort();
for (int w = 1; w < n; w <<= 1, m = p) {
p = 0;
rep(i, n - w + 1, n) se[++p] = i;
rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
Rsort(), swap(rk, se), p = 0;
rep(i, 1, n)
if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
else rk[sa[i]] = ++p;
if (p == n) break;
}
}
void Getheight() {
int h = 0;
rep(i, 1, n) {
if (h) --h;
while (T[i + h - 1] == T[sa[rk[i] - 1] + h - 1]) ++h;
height[rk[i]] = h;
}
}
int ln, Mn[N][LN];
void initST() {
ln = __lg(n);
rep(i, 1, n) Mn[i][0] = height[i];
rep(j, 1, ln)
rep(i, 1, n - (1 << j) + 1) Mn[i][j] = min(Mn[i][j - 1], Mn[i + (1 << (j - 1))][j - 1]);
}
int AskMn(int l, int r) {
int g = __lg(r - l + 1);
return min(Mn[l][g], Mn[r - (1 << g) + 1][g]);
}
ll ans[N];
int f[N];
void initF() {
int r = 0;
vector<int> buc(t + 1, 0);
buc[0] = 114514;
int res = 0;
rep(l, 1, n) {
while (r < n && res < k) {
if (!buc[belongs[sa[++r]]]++) ++res;
}
if (res >= k) f[l] = r;
else f[l] = 2e9;
if (!--buc[belongs[sa[l]]]) --res;
}
}
void Solve() {
rep(i, 1, n) {
int len = suffixlength[sa[i]];
auto check = [&](int x) {
int L = 1, R = n;
{
int l = 2, r = i, mid = 0, res = 1;
while (l <= r) {
mid = (l + r) >> 1;
if (AskMn(mid, i) < x) res = mid, l = mid + 1;
else r = mid - 1;
}
L = res;
}
{
int l = i + 1, r = n, mid = 0, res = n + 1;
while (l <= r) {
mid = (l + r) >> 1;
if (AskMn(i + 1, mid) < x) res = mid, r = mid - 1;
else l = mid + 1;
}
R = res - 1;
}
return R >= f[L];
};
int l = 1, r = len, mid = 0, res = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
ans[belongs[sa[i]]] += res;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> t >> k;
rep(i, 1, t) {
cin >> s[i], T += s[i];
if (i != t) T += '#';
}
n = T.length(), SA(), Getheight(), initST();
int pos = 1;
rep(i, 1, t) {
int len = s[i].length();
rep(j, pos, pos + len - 1)
belongs[j] = i, suffixlength[j] = pos + len - 1 - j + 1;
pos = pos + len + 1;
}
initF(), Solve();
rep(i, 1, t) cout << ans[i] << " \n"[i == t];
return 0;
}
Code 2
log，后缀数组
// log
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 4e5 + 10, LN = 20;
string s[N], T;
int n, m = 27, p, t, k, sa[N], rk[N], se[N], cnt[N], height[N];
void Rsort() {
rep(i, 1, m) cnt[i] = 0;
rep(i, 1, n) ++cnt[rk[i]];
rep(i, 1, m) cnt[i] += cnt[i - 1];
reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
void SA() {
if (n == 1) return (void)(sa[1] = rk[1] = 1);
rep(i, 1, n) rk[i] = ('a' <= T[i - 1] && T[i - 1] <= 'z') ? (T[i - 1] - 'a' + 1) : 27, se[i] = i;
Rsort();
for (int w = 1; w < n; w <<= 1, m = p) {
p = 0;
rep(i, n - w + 1, n) se[++p] = i;
rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
Rsort(), swap(rk, se), p = 0;
rep(i, 1, n)
if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
else rk[sa[i]] = ++p;
if (p == n) break;
}
}
int ln, Mn[N][LN];
void Getheight() {
int k = 0;
rep(i, 1, n) {
if (k) --k;
while (T[i + k - 1] == T[sa[rk[i] - 1] + k - 1]) ++k;
height[rk[i]] = k;
}
}
void initST() {
ln = __lg(n);
rep(i, 1, n) Mn[i][0] = height[i];
rep(j, 1, ln)
rep(i, 1, n - (1 << j) + 1)
Mn[i][j] = min(Mn[i][j - 1], Mn[i + (1 << (j - 1))][j - 1]);
}
int AskMn(int l, int r) {
int k = __lg(r - l + 1);
return min(Mn[l][k], Mn[r - (1 << k) + 1][k]);
}
int f[N], belongs[N];
void initF() {
int r = 0;
vector<int> buc(t + 1, 0);
buc[0] = 114514;
int res = 0;
rep(l, 1, n) {
while (r < n && res < k) {
if (!buc[belongs[sa[++r]]]++) ++res;
}
if (res >= k) f[l] = r;
else f[l] = 2e9;
if (!--buc[belongs[sa[l]]]) --res;
}
}
ll ans[N];
int Suffixlength[N];
void Solve() {
int k = 0;
rep(i, 1, n) {
if (k) --k;
int len = s[belongs[i]].length();
auto check = [&](int x) {
int L = 1, R = n, pos = rk[i];
{
int l = 2, r = pos, mid = 0, res = 1;
while (l <= r) {
mid = (l + r) >> 1;
if (AskMn(mid, pos) < x) res = mid, l = mid + 1;
else r = mid - 1;
}
L = res;
}
{
int l = pos + 1, r = n, mid = 0, res = n + 1;
while (l <= r) {
mid = (l + r) >> 1;
if (AskMn(pos + 1, mid) < x) res = mid, r = mid - 1;
else l = mid + 1;
}
R = res - 1;
}
return R >= f[L];
};
while (k < n - i + 1 && check(k + 1)) ++k;
ans[belongs[i]] += min(Suffixlength[i], k);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> t >> k;
rep(i, 1, t) {
cin >> s[i];
T += s[i];
if (i != t) T += '#';
}
n = T.length(), SA(), Getheight(), initST();
int pos = 1;
rep(i, 1, t) {
int len = s[i].length();
rep(j, pos, pos + len - 1)
belongs[j] = i, Suffixlength[j] = pos + len - 1 - j + 1;
pos = pos + len + 1;
}
initF(), Solve();
rep(i, 1, t) cout << ans[i] << " \n"[i == t];
return 0;
}