408数据结构-字符串

1. 一些定义

• 串中任意多个连续的字符串组成的子序列称为该串的子串，包含子串的串称为主串

• 子串在主串中的位置以子串的第 1 个字符在主串中的位置来表示（以 1 开始）

• 由一个或者多个空格组成的串称为空格串，空格串不是空串

2. 串的模式匹配

2.1 简单匹配

就是直接暴力匹配，$O(nm)$

匹配成功则返回子串在主串中的位置，匹配失败则返回 $0$。

2.2 KMP

KMP算法利用了之前已经匹配的部分的最长公共前后缀，使得主串的指针不会减少，时间复杂度 $O(m+n)$

失配时利用已经匹配部分的最长前后缀，将模式串向右平移，保持了子串前面部分依然和主串匹配。主串的指针得以不变

2.2.1 Next 数组

$Next_i$ 表示当模式串在 $i$ 这个位置失配之后，主串的指针保持不变，继续让主串尝试和 $Next_i$ 这个位置匹配。（$Next$ 数组的处理使得 $[1,Next_i-1]$ 部分仍然和主串是匹配上的。

手动计算做法

首先 $Next_1=0$，$0$ 表示一个特判，如果匹配的时候跳 $Next$ 数组发现跳到 $0$ 的时候，表示主串当前位置已经无法继续匹配了，主串指针需要往前走一位，然后再重新与模式串从头匹配。

对于其他位置，比如我们要求 $Next_i$，则先考虑模式串上，$i$ 之前的部分（即 $[1,i-1]$）的最长公共前后缀（不包含 $[1,i-1]$ 本身）的长度 $len$，于是 $Next_i = len + 1$。

代码实现

上面的做法只是人类比较能直观理解的，如果用代码实现的话，需要用递推的方式来确保时间复杂度。

首先还是 $Next_1 = 0$。

然后对于 $Next_{i+1}$，相当于我们在考虑 $[1,i]$ 的最长公共前后缀长度，那么假设我们已经知道了 $[1, i-1]$ 的最长公共前后缀长度，比如说是 $len$，那么我们只需要判断一下 $len+1$ 和 $i$ 这两个位置字符是否相等，如果也一样的话，那么 $[1,i]$ 的最长公共前后缀长度就是 $len+1$ 了。按 $Next$ 的表示，就是判断一下 $i$ 和 $Next_i$ 是否相等，相等的话 $Next_{i+1} = Next_i + 1$。

如果不一样，那么我们可以再去看 $[1, len]$ 的最长公共前后缀长度，比如说是 $len'$，那么 $[1,len']$ 和 $[len-len'+1，len]$ 相同，由由于 $[1,len]$ 和 $[(i-1)-len+1, (i-1)]$ 是一样的，所以 $[1,len']$ 和 $[(i-1)-len'+1,(i-1)]$ 是一样的，因此可以继续判断 $len'+1$ 和 $i$ 是否一样，以此来推 $[1,i]$ 的最长公共前后缀长度。按$Next$ 的表示，就是判断 $Next_{len+1} = Next_{Next_i}$ 是否和 $i$ 是相等的，相等的话 $Next_{i+1} = Next_{Next_i} + 1$。

上面这个过程是一个递归过程，我们可以一直这样套下去。

c++
1
2
3
4
5
6
7
8
9
10
void get_next(SString T, int next[]) {
    int i = 1, j = 0; // 这里的 j 存的是 next[i]
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) { // 跳 next 跳不动了，或者是字符串相等了
            ++i; ++j; // 我们是从 i 推到 i + 1。同时也完成了 next + 1
            next[i] = j;
        } else j = next[j]; // 继续跳 next 数组
    }
}

匹配就比较简单了：

c++
1
2
3
4
5
6
7
8
9
10
int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1; // i 表示在主串中将要匹配的位置，j 表示在模式串中将要匹配的位置
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            ++i; ++j;
        } else j = next[j];
    }
    if (j > T.length) return i - T.length;
    return 0;
}

2.2.2 Nextval

上面的算法还有一点缺陷，比如：

进一步优化示例

当阴影部分失配的时候，模式串只会一点一点地往右移，并且都会出现失配。

这是因为，如果主串 $i$ 位置和模式串 $j$ 位置发生失配时，$i$ 会继续与 $Next_j$ 匹配，但是 $P_j = P_{Next_j}$ 的话，那么显然这个匹配是不成立的，还需要继续跳 $Next$ 数组。

优化方式是类似并查集那样"路径压缩"：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i; ++j;
            // 下面不太一样
            // 如果不等的话，就和前面一样
            if (T.ch[i] != T.ch[j]) nextval[i] = j;
            // 相等的话需要再往前跳一下
            else nextval[i] = nextval[j];
        } else j = nextval[j];
    }
}

这样计算将会得到 $Nextval$ 数组。

2.3 其他

需要注意的是，上面说的 $Next$ 数组是基于字符串下标从 $1$ 开始这个前提的。如果从 $0$ 开始的话，上面求出来的值都要减一。

上面这个题比较坑的是，$i = j = 5$ 这个位置失配，隐含了字符串下标是从 $0$ 开始的这个条件（如果从 $1$ 开始的话失配就不成立了）