字符串算法（二）：字符串匹配，Border树

[[ slider_text ]]

[[ item.c ]]

字符串算法（二）：字符串匹配，Border树

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

字符串 最小生成树

## 字符串匹配
字符串匹配，可以用 border 来实现，假设模式串是$$t$$，原串是$$s$$，令`str = t + # + s`
然后在`str`上跑 kmp，看一下前缀的哪些位置的`border 值 = |t|`，对应求出$$s$$中的匹配位置

> 这里要求，`#`不能在$$s, t$$中出现过

**如果是一般情况**
同样可以利用 Border 信息做字符串匹配
![](/media/content_img/match01.png)

**[栗酱的数列](https://ac.nowcoder.com/acm/contest/27589/C)**
在$$A$$中找到连续的$$m$$段子序列$$A'$$，满足
```math
(A'_1 + B_1) \bmod k = (A'_2 +B_2) \bmod k = \cdots = (A'_m + B_m) \bmod k
```

> 如果$$k$$很小，是不是很简单？

如果$$k$$很小，可以枚举$$\bmod k \equiv L, L \in [0, k)$$，从而$$A_i \equiv -B_i + L(\bmod k)$$
因为$$B_i, \ k$$都是已知的，可以在$$A$$中找连续的一段，使其等于$$(-B_i + L) \bmod k$$

> 问题是$$k$$很大，怎么做？这个时候不能再从$$\bmod k$$是多少来考虑了

考虑差分
```math
\begin{cases}
(A_1'+B_1) \bmod k \equiv (A_2'+B_2) \bmod k \\
(A_2'+B_2) \bmod k \equiv (A_3'+B_3) \bmod k \\
\vdots \\

(A_{m-1}' + B_{m-1}) \bmod k \equiv (A'_m + B_m) \bmod k
\end{cases}
```
那么在$$\bmod k$$意义下
```math
\begin{cases}
(A_1' - A_2') \equiv -(B_1 - B_2) \\
(A_2' - A_3') \equiv -(B_2 - B_3) \\
\vdots \\
(A_{m-1}' - A_m') \equiv -(B_{m-1} - B_m)
\end{cases}
```
对$$A$$求差分数组，得到$$\text{diff}(A)$$，对$$B$$求差分，并且取`-`，得到$$-\text{diff}(B)$$

对差分数组使用 kmp 即可

**算法实现**
```bash
void solve() {
    int n, m, k;
    cin >> n >> m >> k;

vector<int> a(n+1, 0), b(m+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

vector<i64> da;
    da.push_back(0);
    for (int i = 1; i+1 <= n; i++) da.push_back(safeMod( a[i]-a[i+1], k ));

vector<i64> db;
    db.push_back(0);
    for (int i = 1; i+1 <= m; i++) db.push_back(safeMod( b[i+1]-b[i], k ));

vector<int> next(m+5, 0);

int ans = 0;
    for (int i = 2; i < db.size(); i++) {
        next[i] = next[i-1];
        while (next[i] && db[i] != db[ next[i]+1 ]) next[i] = next[next[i]];
        next[i] += (db[i] == db[ next[i]+1 ]);
    }

for (int i = 1, j = 1; i < da.size(); ) {
        while (j != 1 && da[i] != db[j]) j = next[j-1] + 1;

if (da[i] == db[j]) i++, j++;
        else i++;

if (j == db.size()) {
            ans += 1;
            j = next[db.size()-1] + 1;
        }
    }

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

### 字符串匹配的例子
**[K 匹配](https://ac.nowcoder.com/acm/contest/27589/D)**
给定字符串$$S$$，和模式串$$T$$，$$T$$的长度为$$k$$，如果一个字符串，存在一个位置$$i$$
这个位置能够和$$T$$匹配上，那么把这样的字符串称为$$k$$匹配的
现在问，$$S$$中有多少个**子串**，满足它是 **k-匹配** 的

**算法分析**
不难发现，可以用 kmp 求出满足条件的匹配位置，这些位置是必须的
假设说当前找到了一个匹配位置$$[i, i+k-1]$$，那么怎么分析有多少子串呢？

> 一般考虑 dp，如果直接计数，就考虑**固定左端点，看看右端点有哪些选择？**

1.不难发现，左端点固定$$i$$，右端点可以取$$[i+k-1 \sim n]$$任意一个数
2.左端点能否向左移动？是可以的，但是呢，不能移动到$$1$$
否则，$$[1\sim pos(i-1)]$$这些位置，已经算过一遍了，之后$$[1 \sim pos(i-1) \sim pos(i)]$$又算了一遍

正确的做法是，用$$l$$记一下上一次算到了哪里？
这一轮迭代的时候，只需要考虑左端点从$$[l+1, i]$$中任选即可

综上所述，每个匹配位置$$i$$，对答案的贡献是$$(i-l) \cdot (n - (i+k-1) + 1)$$

## Border 的性质
**性质一**
若$$p, q$$均是$$S$$的周期，那么$$(p, q)$$也是$$S$$的周期

> 证明不难，$$S(i) = S(i+p), S(i) = S(i+q)$$，令$$j = i+p$$，那么$$S(j) = S(i-p+q)$$
从而$$q - p$$也是一个周期，这实际上是辗转相除法，最后可以得到$$(p, q)$$也是其周期

**性质二**
一个串的 Border 数量是$$O(n)$$个，但是他们组成了$$O(\log n)$$个等差数列

## Border 树
对于一个字符串$$S, n = |S|$$，它的 Border 树共有$$n+1$$个节点$$0, 1, 2, \cdots, n$$
其中$$0$$是这棵树的根，对于其他每个点$$i \in [1, n]$$，父节点是$$\text{next}(i)$$
![](/media/content_img/match02.png)

## Trie 树
**字典**，一个字符串的集合称为字典
**字典串**，在字典里的串称为字典串
在处理字符串的时候，遇到一类问题，就是给出一个字典，然后回答很多询问
每次询问，输入一个字符串，判断它是否在字典中
![](/media/content_img/trie01.png)

> 能够支持的操作，插入，删除，查询某个字符串是不是字典串，可持久化

**插入**
假设要插入`ampd`，从根节点开始，看一下有没有`a`的后继，即`tr(x, 'a') = 0 ?`
如果存在这样的后继，就往下走，否则开一个新的节点
后续字符也是同样操作

**删除**
假设删除`boy`，先找到`boy`在`trie`中的位置，然后从**叶子结点开始回溯**
如果某个节点，没有被其他节点用到，直接删掉即可
否则就不能删，同时这个点一直到根的路径都不能删

所以删除操作，只会删掉，叶子结点往上的一小段，满足`deg = 1`的点

当然，也有可能发生，一个点都删不掉的情况，比如删`app`，这个时候取消`app`的**终止标记**即可

### 一些问题
**[假的字符串](https://ac.nowcoder.com/acm/contest/28737/A)**
给你$$n$$个字符串，互不相同，你可以重新定义字典序，求有多少个串能成为字典序最小的串？
比如`ak, a`，因为`a`是`ak`的前缀，有`a`的存在，`ak`是不可能称为字典序最小的串的
即使重新定义字典序`k < a`也不可以

**算法分析**
![](/media/content_img/trie02.png)

### 01-Trie
在 Trie 的应用中，01-Trie 的应用更广
**[奶牛异或](https://ac.nowcoder.com/acm/contest/28737/C)**
给定一个长度`1e5`的正整数数组`a`，定义区间异或和，表示区间所有数异或起来的结果
求区间最大异或和，区间任意指定，只是要求区间异或和最大即可
输出三个数，最大异或和`val`，选择的`[l, r]`分别是多少？

**算法分析**
> 两个相同宽度的二进制数大小（前面不够就补 0）关系，等价于**二进制串的字典序关系**

1.不难想到，先求前缀和，考虑一边遍历$$i$$，一边考虑$$\forall j < i, \ S(i) \oplus S(j)$$的$$\max$$来更新答案

2.遍历的时候，把$$S_j$$作为`01 串`插入`01-Trie`中，前面不够`0`要补上，凑齐`31位`
这样考虑到$$S_i$$的时候，`Trie`中维护了$$j \in [0, i-1]$$所有信息
令$$x \leftarrow S_i$$，考虑$$x$$的每一位

从高位到低位，考虑$$x$$的每一位，`Trie`的指针$$p$$同时往叶子结点走
假设`x`的第`j`位是`bit`，$$p$$优先沿着`!bit`的分支走，如果能走成，`res += (1<<j)`
否则呢，就只能沿着`bit`分支走，走到末尾，即发现是一个$$l$$端点，就可以用`res`更新答案

3.另外，这里还有限制，优先选择奶牛社会等级最高的，也就是$$i$$要尽量小
那么在遍历$$i$$的时候，仅当$$res > maxv$$的时候，才更新$$r \leftarrow i$$，相等时候不更新
另一个限制，还不唯一，选择最短的，怎么办呢？
也就是说，$$res = maxv$$的时候，要使得$$[j, i]$$，$$j$$尽可能大？

注意到`Trie`的插入，不是有一个**终止标记**吗？插入$$S_j$$的时候，相应的末尾节点
终止标记记为$$j$$，如果原来就有终止标记了，用新的$$j$$去覆盖它
这样就保证了对于每一个$$i$$，$$[j, i]$$最短

**[最大异或和](https://ac.nowcoder.com/acm/contest/28737/D)**
给定长度为$$n$$的数组$$a$$，再给出$$q$$次操作，$$3e5$$级别的
1.修改操作，将数字$$x$$添加到数组末尾，数组长度从$$n \to n + 1$$
2.查询操作，求$$[l, r]$$内的$$p$$，使得$$a(p) \oplus a(p+1) \cdots \oplus a(n) \oplus x$$最大

**算法分析**
不难发现，要使得$$x \oplus S(n) \oplus S(p')$$最大，而$$val \leftarrow x \oplus S_n$$是定值
等价于找一个$$l-1 \leqslant p' \leqslant r-1$$，使得$$S(p') \oplus val$$最大

> 难点在于，如何保证 01-Trie 中仅有$$[l-1, r-1]$$之间的元素？

**对 01-Trie 进行可持久化**，可持久化的要点如下
![](/media/content_img/trie03.png)

> 新旧版本指针，同时从根往下走
新版本，插入的数，要修改哪些指针？就把旧版本 fork 一份，并且基于 fork 出来的旧版本去更改
其他指针，直接复制旧版本的即可

### 可持久化 trie 算法实现
```bash
namespace Trie {
    const int N = 6e5 + 5;
    const int LOG = 30;

int root[N];
    int trie[N * 32][2], cnt[N * 32];
    int tot = 0;

int newNode() {
        int x = ++tot;
        fill(trie[x], trie[x]+2, 0);
        cnt[x] = 0;
        return x;
    }

// usage: root[i] = insert(root[i-1], a[i])
    // idx start from [1...n]
    int insert(int pid, int x) {
        int nid = ++tot;

int p = nid, q = pid;
        for (int i = LOG; i >= 0; i--) {
            cnt[p] = cnt[q] + 1;

int c = (x >> i & 1);

if (!trie[p][c]) trie[p][c] = newNode();
            trie[p][!c] = trie[q][!c];

p = trie[p][c], q = trie[q][c];
        }
        cnt[p] = cnt[q] + 1;
        return nid;
    }

// query, [l...r]， ^x kth element
    // usage: query(root[l-1], root[r], x)
    int query(int lid, int rid, const int x) {
        int p = lid, q = rid;
        // [q, p]

int res = 0;
        for (int i = LOG; i >= 0; i--) {
            int c = (x >> i & 1);
            if ( (cnt[ trie[p][!c] ] - cnt[ trie[q][!c] ])  ) {
                res |= (1 << i);
                p = trie[p][!c], q = trie[q][!c];
            }
            else {
                p = trie[p][c], q = trie[q][c];
            }
        }
        return res;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

vector<int> s(n + m + 10, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s[i] = s[i-1] ^ x;
    }

for (int i = 1; i <= n; i++) {
        Trie::root[i] = Trie::insert(Trie::root[i-1], s[i]);
    }

for (int i = 0; i < m; i++) {
        string op;
        cin >> op;

if (op[0] == 'A') {
            int x;
            cin >> x;

n += 1;
            s[n] = s[n-1] ^ x;
            Trie::root[n] = Trie::insert(Trie::root[n-1], s[n]);
        }
        else {
            int l, r, x;
            cin >> l >> r >> x;
            l--, r--;

auto val = x ^ s[n];

if (l == 0) {
                auto res = Trie::query(Trie::root[0], Trie::root[r], val);
                chmax(res, val);
                cout << res << "\n";
            }
            else {
                auto res = Trie::query(Trie::root[l-1], Trie::root[r], val);
                cout << res << "\n";
            }
        }
    }
}
```

### 01-Trie 其他应用
**[Educational Codeforces Round 32 G. Xor-MST](https://codeforces.com/contest/888/problem/G)**
**问题描述**
给定一个$$n \leqslant 2e5$$的无向**完全图**，每一个点$$u$$的点权为$$0 \leqslant A_u \leqslant 2^{30}$$
任意两个点之间的边权是$$A_u \oplus A_v$$，求最小生成树

**算法分析**
> kruskal 算法肯定行不通，考虑能不能用 prim 算法，借鉴一下 prim 算法的思路
![](/media/content_img/trie04.png)

prim 算法保证收敛性和复杂度的一些操作

1.堆顶元素一定会进$$S$$集合

2.考虑$$S-T$$边的时候，用$$S$$集合中的点$$u$$，$$w(u, v)$$去更新$$key(v)$$
当$$key(v) < w(u, v)$$的时候，说明$$v$$**已经被之前$$S$$集中的点选上了，并且之前选的点更优**
在这种情况下，$$(key_v, v)$$是不会作为侯选点来考虑的

每一轮迭代，我们只在$$v$$**存在更小的，连向$$S$$集的边**的时候，才把$$v$$选到优先队列中
进入迭代，这样可以保证每一次迭代，都可以使得`key(v)`变得更小
当`key(v)`取得最小值的时候迭代结束，所以这个算法一定收敛

另外需要注意的是，优先队列中可能存在同一个点$$v$$，有**两种不同的 key**
原因是后续迭代中发现更小的`S-T`边，$$v$$重复进优先队列了
这种情况下我们只会取**最小的 key **加入$$S$$集，并且把相应的点标记为`ins[v] = true`处理过
迭代的时候，遇到处理过的点，直接跳过即可

#### Boruvka 算法
![](/media/content_img/brouvka01.png)
![](/media/content_img/brouvka02.png)
![](/media/content_img/brouvka03.png)
![](/media/content_img/brouvka04.png)

#### 算法实现

```bash
namespace Trie {
    const int N = 2e5 + 5;
    const int LOG = 30;

int root[N];
    int trie[N * 50][2], sz[N * 50], tag[N * 50];
    int tot = 0;

int newNode() {
        int x = ++tot;
        fill(trie[x], trie[x]+2, 0);
        sz[x] = tag[x] = 0;
        return x;
    }

void insert(int &rt, const int x, int idx) {
        if (rt == 0) rt = newNode();

int p = rt;
        sz[p] += 1;
        for (int i = LOG; i >= 0; i--) {
            int c = x >> i & 1;
            if (!trie[p][c]) trie[p][c] = newNode();
            p = trie[p][c];

sz[p] += 1;
        }
        tag[p] = idx;
    }

void merge(int &p, int q) {
        if (!p || !q) {
            p += q;
            return;
        }
        merge(trie[p][0], trie[q][0]);
        merge(trie[p][1], trie[q][1]);

sz[p] = sz[ trie[p][0] ] + sz[ trie[p][1] ];
        tag[p] = tag[q];
    }

pair<int, int> query(int lhs, int rhs, const int x) {
        // trie[lhs] - trie[rhs]
        int p = lhs, q = rhs;

int res = 0;
        for (int i = LOG; i >= 0; i--) {
            int c = x >> i & 1;

// debug(sz[ trie[p][c] ]);
            if ( (sz[ trie[p][c] ] - sz[ trie[q][c] ]) > 0 ) {
                p = trie[p][c], q = trie[q][c];
                //debug(p);
            }
            else {
                p = trie[p][!c], q = trie[q][!c];
                res |= (1<<i);
            }
        }        
        return {res, tag[p]};
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

sort(a.begin()+1, a.end());
    a.erase(unique(a.begin()+1, a.end()), a.end());
    n = a.size() - 1;
    
    // debug(a);

// debug(n);
    DSU<int> dsu(n+5);
    for (int i = 1; i <= n; i++) {
        Trie::insert(Trie::root[0], a[i], i);
        Trie::insert(Trie::root[i], a[i], i);
    }

vector<int> link(n+1, 0);
    i64 ans = 0;

while (true) {
        bool ed = true;

vector<int> key(n+1, inf<int>);
        for (int i = 1; i <= n; i++) {
            auto x = dsu.find(i);
            auto [w, j] = Trie::query(Trie::root[0], Trie::root[x], a[i]);
            auto y = dsu.find(j);

if (x == y) continue;

if (key[x] > w) key[x] = w, link[x] = y;
            if (key[y] > w) key[y] = w, link[y] = x;

//debug(w);
        }

for (int i = 1; i <= n; i++) {
            if (key[i] == inf<int>) continue;

// (i, link(i))
            if (dsu.same(i, link[i])) continue;
            ed = false;
            auto x = dsu.find(i), y = dsu.find(link[i]);

ans += 1LL * key[i];
            dsu.merge(x, y), Trie::merge(Trie::root[x], Trie::root[y]);
        }
        // debug(ans);

if (ed) break;
    }
    cout << ans << "\n";
}
```

上一篇：字符串算法（一）：Z 函数，kmp 算法下一篇：字符串算法（三）：Border 树

看完文章有啥想法