字符串算法（三）：Border 树

[[ slider_text ]]

[[ item.c ]]

字符串算法（三）：Border 树

发布时间 2025-02-08 作者：zhangminchen 来源：算法小站

trie 树上倍增 树链剖分 分治

## Border 树的应用
> 简单的一些性质

1) 每个前缀`prefix[i]`的所有 Border，是节点`i`到根的链
2) 哪些**前缀**有长度为`x`的`Border`？`x`的子树（一般来说，Border 树上节点值，表示 Border 长度）
3) 求两个前缀的公共 Border，等价于求 LCA

> 求前缀 p，q 的最长公共 border

```bash
void solve() {
    // ...
    auto next = kmp(str);
    vector<vector<int> > g(n+1);
    for (int i = 1; i <= n; i++) {
        int pa = next[i];
        g[pa].push_back(i);
    }

vector<int> dep(n+1, 0);
    vector<vector<int> > up(n+1, vector<int>(20, -1));

function<void(int, int)> dfslca = [&](int u, int fa) {
        // 与普通 lca 不同
        dep[u] = (fa == -1 ? 0 : dep[fa]) + 1;
        
        for (auto v : g[u]) {
            if (v == fa) continue;
            up[v][0] = u;
            dfslca(v, u);
        }
    };
    // N 是节点个数
    auto prework = [&](int N) -> void {
        // 注意，倍增求lca要保证 dep[root] = 1
        // dep[1] = 1;
        dfslca(0, -1);
        
        for (int i = 1; i < 20; i++) {
            for (int u = 1; u <= N; u++) {
                up[u][i] = (up[u][i-1] == -1 ? -1 : up[ up[u][i-1] ][i-1]);
            }
        }
    };

prework(n);

function<int(int, int)> lca = [&](int x, int y) {
        if (dep[x] > dep[y]) swap(x, y);
        for (int i = 19; i >= 0; i--) {
            if (dep[up[y][i]] >= dep[x]) y = up[y][i];
        }
        if (x == y) return x;
        for (int i = 19; i >= 0; i--) {
            if (up[y][i] != up[x][i]) y = up[y][i], x = up[x][i];
        }
        return up[x][0];
    };

// 求 lca
    res = lca(p, q);
    if (res == min(p, q)) res = up[res][0];
}
```

### 一些问题
**[葫芦和斌斌的字符串1](https://ac.nowcoder.com/acm/contest/28737/F)**
给定长度为$$n$$的串$$S$$，一个正整数$$k$$，求最长字符串$$T$$，满足
1.$$T$$是$$S$$的前缀
2.$$T$$是$$S$$的后缀
3.$$T$$在$$S$$中至少出现$$k$$次

**算法分析**
注意到，$$T$$一定是$$S$$的 Border，所以满足条件的$$T$$
一定在** Border 树中**，从$$n \to \text{root}$$的路径上

那么怎么保证最长，且出现次数为$$\geqslant k$$次呢？

只需要从$$n$$往父亲跳，如果发现**子树大小**$$\geqslant k$$，就可以返回了

> Border 树中$$u$$的子树大小，就是长度为$$u$$的串，作为`Border`出现的次数

**[葫芦和斌斌的字符串2](https://ac.nowcoder.com/acm/contest/28737/G)**
和上一个问题基本一样，多了一些操作
1.修改操作，在字符串末尾添加一个字符`ch`
2.查询操作，`2 k`，求一个最长的字符串$$T$$，同时满足$$T$$是$$S$$的前缀，$$T$$是$$S$$的后缀
并且$$T$$在$$S$$中至少出现了$$k$$次

**算法分析**
![](/media/content_img/border-tree.png)

**算法实现**
```bash
const int LOG = 20;

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

str = " " + str;
    int idx = n;

// [1...n] [n+1...idx]
    vector<PII> ops;
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;

if (op == 1) {
            char ch;
            cin >> ch;
            str.push_back(ch);
            ops.push_back( {op, ++idx} );
        }
        else {
            int K;
            cin >> K;
            ops.push_back( {op, K} );
        }
    }

int N = idx;
    // assert(N == str.size() - 1);
    vector<int> sz(N+5, 0);
    for (int i = 1; i <= n; i++) sz[i] = 1;

// border tree
    auto next = kmp(str);
    vector<vector<int> > g(N+1);
    for (int i = 1; i <= N; i++) {
        int x = i, y = next[i];
        g[x].push_back(y), g[y].push_back(x);
    }

// dfs get size
    vector<vector<int> > go(N+1, vector<int>(LOG+1, -1));
    auto dfs = [&](auto &dfs, int u, int fa) -> void {
        go[u][0] = fa;
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(dfs, v, u);
            sz[u] += sz[v];
        }
    };
    auto updgo = [&]() -> void {
        for (int i = 1; i <= LOG; i++) {
            for (int u = 1; u <= N; u++) {
                go[u][i] = (go[u][i-1] == -1 ? -1 : go[ go[u][i-1] ][i-1]);
            }
        }
    };

dfs(dfs, 0, -1);
    updgo();
    // debug(sz);

// HLD and fenwick
    HLD hld(0, g);
    Fenwick<int> tr(N+5);

// query on tree
    auto query = [&](int u, int K) -> int {
        int res = -1;

int now = u;
        for (int i = LOG; i >= 0; i--) {
            auto to = go[now][i];
            if (to > 0) {
                auto d = tr.sum( hld.l[to] );
                auto SZ = d + sz[to];

if (SZ < K) now = to; 
            }
        }
        if (now == -1) return -1;

now = go[now][0];
        if (now > 0) {
            auto d = tr.sum( hld.l[now] );
            auto SZ = d + sz[now];

if (SZ >= K) return now;
        }
        return -1;
    };

int last = n;
    for (auto [op, idx] : ops) {
        if (op == 1) {
            auto path = hld.path(idx, 0);
            for (auto [l, r] : path) {
                tr.add(l, 1), tr.add(r+1, -1);
            }
            last = idx;
        }
        else {
            auto res = query(last, idx);
            if (res <= 0) res = -1;
            cout << res << "\n";
        }
    }
}
```

## 分治策略
**[区间异或和异或区间最大值异或区间最小值](https://ac.nowcoder.com/acm/contest/28737/E)**
**问题描述**
给定一个序列，定义区间的代价是
```math
\text{xorsum} \oplus \max \oplus \min
```
分别表示区间所有数异或和，区间的最大值，区间的最小值
现在给你一个序列$$a$$，求所有区间中，区间代价**最大**是多少

**算法分析**
![](/media/content_img/trie-divide01.png)
![](/media/content_img/trie-divide02.png)
![](/media/content_img/trie-divide03.png)
![](/media/content_img/trie-divide04.png)

### 算法实现
```bash
void solve() {
    int n;
    cin >> n;
    vector<i64> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

i64 ans = 0;

vector<i64> premax(n+5, -inf<i64>), premin(n+5, inf<i64>), rsum(n+5, 0);

auto calc = [&](auto &calc, int l, int r) {
        if (l >= r) {
            chmax(ans, a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        calc(calc, l, mid), calc(calc, mid+1, r);

// prework

for (int i = mid + 1; i <= r; i++) {
            if (i == mid + 1) {
                premax[i] = premin[i] = rsum[i] = a[i];
            } 
            else {
                rsum[i] = rsum[i-1] ^ a[i];
                premax[i] = max(premax[i-1], a[i]);
                premin[i] = min(premin[i-1], a[i]);
            }
        }

// [ lmin, lmax, lsum ] [ rsum ]
        Trie::clear();
        i64 lmin = inf<i64>, lmax = -inf<i64>, lsum = 0;
        
        int j = mid;
        for (int i = mid; i >= l; i--) {
            chmin(lmin, a[i]), chmax(lmax, a[i]), lsum ^= a[i];
            while (j + 1 <= r && premin[j+1] >= lmin && premax[j+1] <= lmax) {
                j += 1;
                Trie::insert(rsum[j]);
            }
            auto res = Trie::query(lmin ^ lmax ^ lsum);
            chmax(ans, res);
        }

// [ lmin, lsum ] [ rmax, rsum ]
        Trie::clear();
        lmin = inf<i64>, lmax = -inf<i64>, lsum = 0;

int p = mid;
        j = mid;

for (int i = mid; i >= l; i--) {
            chmin(lmin, a[i]), chmax(lmax, a[i]), lsum ^= a[i];

while (p + 1 <= r && premin[p+1] >= lmin) {
                p += 1;
                Trie::insert( premax[p] ^ rsum[p] );
            }
            if (p < mid + 1) continue;

while (j + 1 <= p && premax[j + 1] < lmax) {
                j += 1;
                Trie::del( premax[j] ^ rsum[j] );
            }

auto res = Trie::query(lmin ^ lsum);
            chmax(ans, res);
        }
    };

calc(calc, 1, n);
    reverse(a.begin()+1, a.end());
    calc(calc, 1, n);

cout << ans << "\n";
}
```

上一篇：字符串算法（二）：字符串匹配，Border树下一篇：2025年一月算法比赛（二）

看完文章有啥想法