字符串算法（一）：Z 函数，kmp 算法

[[ slider_text ]]

[[ item.c ]]

字符串算法（一）：Z 函数，kmp 算法

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

字符串 kmp Z函数

## Z 函数
字符串下标从$$0$$开始，$$Z(i)$$表示$$s[0\cdots]$$和$$s[i\cdots ]$$的**最长公共前缀（LCP）**的长度
也就是说，$$s$$从$$i$$下标开始走，能和$$s$$从`0`开始匹配上的最长子串是$$s[i, i+Z_i-1]$$

### Z函数的相关算法和性质
**朴素算法**
根据暴力来求解即可
```bash
while (i +Z[i] < n && s[Z[i]] == s[i+Z[i]])		Z[i]++;
```

现在考虑怎么优化
> 优化的关键，是在于计算$$Z(i)$$的时候，利用已经计算好的$$Z(0), Z(1), \cdots, Z(i-1)$$的信息
需要关心之前的下标，**最远能走到哪里**？已经走过的段，不需要再继续走了

![](/media/content_img/Zfun01.png)
![](/media/content_img/Zfun02.png)

```bash
vector<int> Z(string str) {
    int n = str.size();
    vector<int> z(n+1);

z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = max(0, min(z[i-j], j + z[j] - i));
        while (i + z[i] < n && str[z[i]] == str[ i+z[i] ]) {
            z[i]++;
        }

if (i + z[i] > j + z[j]) j = i;
    }
    return z;
}
```

### Z函数有关的推论
#### 匹配所有子串
记$$t$$是文本串，$$p$$是模式串，求文本串中，模式串$$p$$所有出现的位置
![](/media/content_img/Zfun03.png)

#### 本质不同的子串数
![](/media/content_img/Zfun04.png)

#### 字符串的整周期
![](/media/content_img/Zfun05.png)

## KMP 算法
### 一些重要的定义
**Border**
如果一个字符串$$S$$，同一个长度的前缀和后缀完全相同，那么就称前缀（后缀）是一个 Border
比如说，`S = bbabbab`，那么`{b, bbab}`是`Border`

**周期和循环节**
对于字符串$$S$$和正整数$$p$$，如果有$$S[i] = S[i - p]$$，对于$$\forall i \in (p, |S|]$$成立
那么称$$p$$是字符串$$S$$的一个循环周期

比如`S = bbabbab`
```bash
p = 3,		bba 是一个循环周期
p = 6,		bbabba 是一个循环周期
p = 7,		bbabbab 一整个串也是一个循环周期
```

注意，循环**周期**可以**不完整地出现**，但是循环节，要满足$$p \mid n$$
也就是说，**循环节**$$|p|$$必须**完整地出现，并拼接在一起**

**Border 和周期重要的性质**
如果$$p$$是$$S$$的周期 $$\Longleftrightarrow \quad |S|-p$$是$$S$$的 Border

> 证明如下
如果$$p$$是$$S$$的周期，$$\Leftrightarrow \quad S(i-p) = S(i)$$
如果$$q$$是$$S$$的 Border，$$\Leftrightarrow \quad S[1\cdots q] = S[n-q+1, n]$$，拆开之后
```bash
S[1] = S[n-q+1]
S[2] = S[n-q+2]
....
S[q] = S[n]
```
从而我们可以推出$$S(i) = S(i+n-q)$$，从而$$n-q$$是串的一个周期，从而$$p+q = |S|$$

**特别注意**
**Border** 是不具有二分性质的

### 算法初步
根据之前的分析，求周期，也等价于求 Border

> 朴素算法
对于$$1 \leqslant i \leqslant |S|$$，暴力检查是否有$$pre(i) = suf(i)$$，$$O(n^2)$$复杂度

用字符串哈希的时候，可以把复杂度做到$$O(n)$$，但是容易有哈希冲突

**Border的性质**
![](/media/content_img/kmp01.png)
![](/media/content_img/kmp02.png)

**KMP 算法的实现**
```bash
vector<int> kmp(const string &s) {
    string str = s;
    int n = (str[0] == ' ' ? str.size() - 1 : str.size());
    if (str[0] != ' ') str = " " + str;

vector<int> f(n+2, 0);
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1];
        while (f[i] && str[i] != str[ f[i]+1 ]) f[i] = f[f[i]];
        f[i] += (str[i] == str[f[i] + 1]);
    }

return f;
}
```

### 一些问题
**[KMP字符串匹配](https://ac.nowcoder.com/acm/contest/27589/A)**
第一，求$$s2$$在$$s1$$中出现的所有位置
第二，求关于$$s2$$的，长度为$$i$$的前缀的最长 border 长度

**[字符串的问题](https://ac.nowcoder.com/acm/problem/15165)**
给定一个串$$S$$，求它的最长子串$$T$$，满足$$T$$是$$S$$的 Border，同时，$$T$$在其他位置还需要再出现一次

![](/media/content_img/kmp03.png)

**[carpet](https://ac.nowcoder.com/acm/problem/16638)**
有一个$$n \times m$$的字符串二维矩阵$$A$$，求一个最小的子矩阵$$B$$，使得
把矩阵$$B$$横向纵向无限复制之后，$$A$$是一个子矩阵
实际上，就是求$$A$$的二维循环周期

还有一个问题，就是说你求出这个周期$$p \times q$$，现在你有一个`p * q`的方框
在$$A$$上移动，方框框起来的元素取最大值，你要移动这个方框，使得最大值最小

**算法分析**
二维循环周期，对$$x, y$$两个维度分别求，完全是对称的
> 横向怎么求？
横向循环周期，同时是每一行的循环周期，于是对每一行分别求循环周期（KMP）
然后求出最小的，公共循环周期即可

> 移动方框，使最大值最小，这一部分可以用**单调队列**来解决

![](/media/content_img/kmp04.png)
![](/media/content_img/kmp05.png)

上一篇：匈牙利算法，二分图带权匹配下一篇：字符串算法（二）：字符串匹配，Border树

看完文章有啥想法