Border树
title: Border树
categories:
- ICPC
tags:
- null
abbrlink: e3b02275
date: 2023-06-17 00:00:00
Border树
对于一个字符串S,n = |S|,它的Border 树(也叫next 树)共有n+1
个节点:0, 1, 2, . . . , n。
0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n,父节点为next[i]。
struct KMP {
vector<int> nxt;
string tt;
int len;
KMP() {}
KMP(string t) {
len = t.size();
t = " " + t;
tt = t;
nxt.resize(len + 1);
nxt[1] = nxt[0] = 0;
init(tt);
}
void init(string t) {
for (int i = 2; i <= len; i++) {
nxt[i] = nxt[i - 1];
while (nxt[i] && t[i] != t[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
nxt[i] += (t[i] == t[nxt[i] + 1]);
}
}
void buildtree(auto& e) {
for (int i = 1; i <= len; i++) {
e[nxt[i]].emplace_back(i);
}
}
};
性质:next[i] 表示字符串 S 的前缀 Prefix[i] 的非平凡的最大 Border。
- 每个前缀Prefix[i] 的所有Border:节点i 到根的链。
- 哪些前缀有长度为x 的Border:x 的子树。前缀x出现了子树大小siz[x]次
- 求两个前缀的最长公共Border 等价于求LCA。
1.给定一个字符串 $s$,定义它的 $k$ 前缀 $\mathit{pre}k$ 为字符串 $s{1\dots k}$,$k$ 后缀 $\mathit{suf}k$ 为字符串 $s{|s|-k+1\dots |s|}$,其中 $1 \le k \le |s|$。
定义 $\bold{Border}(s)$ 为对于 $i \in [1, |s|)$,满足 $\mathit{pre}_i = \mathit{suf}_i$ 的字符串 $\mathit{pre}_i$ 的集合。$\bold{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。
有 $m$ 组询问,每组询问给定 $p,q$,求 $s$ 的 $\boldsymbol{p}$ 前缀 和 $\boldsymbol{q}$ 前缀 的 最长公共 $\operatorname{border}$ 的长度。
Sol:建立border树,等价于求两者的lca。由于求的是非平凡,如果存在一个前缀是另一个前缀的border,则需要跳到父亲
debug:树剖的板子要加双向边并且注意坐标偏移从1-n+1
void solve() {
string s;cin >> s; KMP kmp(s);
int n = s.size();HLD hld(n + 1);// 字符串长度加上一个空节点
for (int i = 1; i <= kmp.len; i++) { // 一定要加双向边
hld.addEdge(kmp.nxt[i] + 1, i + 1);
hld.addEdge(i + 1, kmp.nxt[i] + 1);
}
hld.work(1);
int m;cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
x++;//进行下标偏移。考虑到dfs序问题(0-n)->(1-n+1)
y++;
int res = hld.lca(x, y);
if (x == res || y == res)//如果一个前缀是另一个前缀border,找父亲
cout << hld.parent[res] - 1 << endl;
else
cout << res - 1 << endl;
}
}
//倍增版本
void solve() {
string s;
cin >> s;
KMP kmp(s);
int n = s.size();
Blca lc(n + 1); // 字符串长度加上一个空节点
for (int i = 1; i <= kmp.len; i++) { // 一定要加双向边
lc.add(kmp.nxt[i] + 1, i + 1);
}
lc.dfs(1, 0);
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
x++; // 进行下标偏移。考虑到dfs序问题(0-n)->(1-n+1)
y++;
int res = lc.lca(x, y);
if (x == res || y == res) // 如果一个前缀是另一个前缀border,找父亲
cout << lc.st[res][0] - 1 << endl;
else
cout << res - 1 << endl;
}
}
2.字符串S 长度不超过106,求一个最长的子串T,满足:
T 为S 的前缀。
T 为S 的后缀。
T 在S 中至少出现K次。
Sol:考虑T是border,出现k次等价于子树比k大,我们只需要把树建出来,然后dfs一遍求子树大小就可以了
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
KMP kmp(s);
vector<vector<int>> e(n + 1);
kmp.buildtree(e);
vector<int> sz(n + 1);
auto dfs = [&](auto self, int u)->void {
sz[u] = 1;
for (auto v : e[u]) {
self(self, v);
sz[u] += sz[v];
}
};
dfs(dfs,0);
int ans = 0;
for (int i = n; i; i = kmp.nxt[i]) {
if (sz[i] >= k)
ans = max(ans, i);
}
if(ans==0)cout<<-1;else cout<<s.substr(0,ans);
}
3.字符串S 长度不超过200, 000,有Q ≤ 200, 000 次操作:
修改操作:向字符串末尾添加一个字符ch。
查询操作:求一个最长的子串T,满足:
T 为S 的前缀。
T 为S 的后缀。
T 在S 中至少出现K次。
Sol:考虑离线询问,先把完整的fail树建立。然后每次询问的子树大小,我们动态维护标记,从当前结尾开始倍增每次用树状数组查询带标记子树大小。倍增需要特判一开始就满足条件的情况。
debug:两层for变量用重,导致RE。倍增需要特判一开始就满足条件的情况。由于树状数组下标不能为0,而fail树中存在0号节点,但dfs序我们又规定了从1开始标号,每次都是在dfs序的意义下修改树状数组,所以不需要偏移了。牢记Fwk初始化都传入节点数就可以了
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
int cnt = n;
vector<node> q(m + 1);
for (int i = 1; i <= m; i++) {
cin >> q[i].op;
if (q[i].op == 1) {
cin >> q[i].c;
s += q[i].c;
cnt += 1;
q[i].x = cnt;
} else {
cin >> q[i].x;
}
}
deb(s);
KMP kmp(s);
Blca lc(cnt + 1);
kmp.buildtree(lc.e);
lc.dfs(0, 0);
Fwk<int> fw(cnt + 1); // 树状数组下标偏移
for (int i = 1; i <= n; i++) fw.add(l[i], 1);
// 主要是建树
int p = n;
for (int i = 1; i <= m; i++) {
if (q[i].op == 1) {
p = q[i].x;
fw.add(l[p], 1);
} else {
int cur = p;
if (fw.rangeSum(l[cur] - 1, r[cur]) >= q[i].x) {
cout << cur << endl;
continue;
}
for (int j = lc.len; j >= 0; j--) {
int pos = lc.st[cur][j];
deb(pos, fw.rangeSum(l[pos] - 1, r[pos]));
if (fw.rangeSum(l[pos] - 1, r[pos]) < q[i].x)
cur = pos;
}
deb(cur);
if (lc.st[cur][0])
cout << lc.st[cur][0] << endl;
else
cout << -1 << endl;
}
deb(i, p);
}
}
可持久化KMP,nxt图(类比triw图
https://codeforces.com/contest/1721/problem/E
https://www.cnblogs.com/Blue233333/p/8241503.html