数组结构之串

简单的模式匹配算法

概念：
模式匹配是指在主串中查找某个子串（模式串）的过程。如果找到了，返回该子串在主串中的位置；如果没有找到，则返回 0。

算法描述

以下是简单的暴力模式匹配算法的伪代码实现：

int Index(sstring s, sstring T) {
    int i = 1, j = 1; // 初始化指针 i 和 j，分别指向主串和模式串的起始位置
    while (i <= S.length && j <= T.length) { // 遍历主串和模式串
        if (s.ch[i] == T.ch[j]) { // 字符匹配
            ++i; // 移动到下一个字符
            ++j; // 移动到模式串的下一个字符
        } else { // 字符不匹配
            i = i - j + 2; // 重新定位主串的指针
            j = 1; // 重置模式串的指针
        }
    }
    if (j > T.length) // 如果模式串的指针 j 超过了模式串的长度，表示匹配成功
        return i - T.length; // 返回匹配开始的位置
    else
        return 0; // 如果未找到匹配，返回 0
}

变量解释

sstring s: 主串（即待搜索的字符串）。
sstring T: 模式串（即要查找的子串）。
i: 主串的当前索引，从 1 开始（注意：实际实现时索引可能从 0 开始，需要调整）。
j: 模式串的当前索引，从 1 开始。
s.ch[i]: 主串 s 中的第 i 个字符。
T.ch[j]: 模式串 T 中的第 j 个字符。

算法步骤

初始化: 将两个指针 i 和 j 分别指向主串和模式串的起始位置。
比较字符:
- 如果 s.ch[i] 等于 T.ch[j]，则继续比较后续字符，将 i 和 j 都向后移动一个位置。
- 如果不匹配，则将 i 移动到 i - j + 2，将 j 重置为 1，重新开始匹配。
返回结果:
- 如果 j 超过了模式串的长度，说明找到了匹配，返回 i - T.length（即匹配的起始位置）。
- 如果未找到匹配，返回 0。

算法复杂度

时间复杂度: 在最坏情况下，时间复杂度为 \(O(n \times m)\)，其中 \(n\) 是主串的长度，\(m\) 是模式串的长度。
空间复杂度: \(O(1)\)，仅使用了常数级别的额外空间。

示例

假设主串 s 为 "abcde" 和模式串 T 为 "cd"：

初始状态：i = 1, j = 1
进行字符比较：
- s.ch[1] 是 'a', 不匹配，重新开始。
- s.ch[2] 是 'b', 不匹配，重新开始。
- s.ch[3] 是 'c', 匹配，继续。
- s.ch[4] 是 'd', 匹配，继续。
此时 j 超过了模式串的长度，返回 i - T.length，结果为 4 - 2 = 2。

KMP 算法

KMP 算法用于在主串中寻找子串的匹配，具有更高的效率，其时间复杂度为 \(O(m+n)\)，其中 \(m\) 是主串的长度，\(n\) 是模式串的长度。相比之下，普通的暴力匹配算法时间复杂度为 \(O(m \times n)\)。

KMP 算法的核心思想

KMP 算法的主要思想是利用部分匹配信息来避免不必要的比较。当发生字符不匹配时，利用已知的部分匹配信息，直接将模式串的指针移动到合适的位置，而不是简单地将主串指针移动到下一个字符。

`next` 数组

next 数组用于记录模式串中每个字符的最长相等前缀后缀的长度。它帮助在失配时决定模式串的移动位置。

`next` 数组的构建

初始化: 设定 next[1] = 0，即模式串的第一个字符没有相等的前缀。
遍历构建: 通过两个指针 i 和 j 遍历模式串：
- 如果 T.ch[i] == T.ch[j]，则有新的匹配，更新 j 并将 next[i] 设为 j。
- 如果 T.ch[i] ≠ T.ch[j]，则将 j 移动到 next[j]，继续比较，直到找到匹配或 j 变为 0。

伪代码实现如下：

void get_next(string T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0; // 模式串的第一个字符没有前缀后缀
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i; 
            ++j; 
            next[i] = j; // 记录匹配长度
        } else {
            j = next[j]; // 移动 j 指针
        }
    }
}

KMP 算法的实现

在 KMP 算法的主匹配函数中，利用 next 数组来调整模式串的位置：

int Index_KMP(string s, string T, int next[]) {
    int i = 1, j = 1; // 初始化指针
    while (i <= s.length && j <= T.length) {
        if (j == 0 || s.ch[i] == T.ch[j]) {
            ++i; 
            ++j; // 继续比较后继字符
        } else {
            j = next[j]; // 利用 next 数组调整 j 指针
        }
    }
    if (j > T.length) // 如果匹配成功
        return i - T.length; // 返回匹配起始位置
    else
        return 0; // 未找到匹配
}

`next` 数组的优化：`nextval` 数组

在某些情况下，next 数组可能会导致不必要的比较。为了解决这个问题，可以引入 nextval 数组，该数组在 next 数组的基础上进一步优化。

递归调整: 如果在比较中发生不匹配，并且当前字符与 next[j] 位置的字符相同，则可以将 next[j] 更新为 next[next[j]]，直到两个字符不再相等。

伪代码实现如下：

void get_nextval(string 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; 
            nextval[i] = j; // 记录匹配长度
        } else {
            j = nextval[j]; // 移动 j 指针
        }
        // 优化部分
        if (T.ch[i] != T.ch[j]) {
            nextval[i] = nextval[j]; // 更新
        } else {
            nextval[i] = j; // 否则正常记录
        }
    }
}

总结

KMP 算法的优点在于：

避免回溯: 主串不回溯，只是通过 next 或 nextval 数组的计算来调整模式串的位置。
高效匹配: 尤其在主串与模式串中存在多个相同字符时，KMP 算法能显著提高匹配效率。

尽管普通模式匹配的实际执行时间在许多情况下接近 \(O(m+n)\)，KMP 算法在部分匹配的场景下展示了明显的优势。

选择题

1. 设有两个串 \(S\) 和 \(T\)，求 \(T\) 在 \(S\) 中首次出现的位置的运算称为()

A. 求子串
B. 判断是否相等
C. 模式匹配
D. 连接

答案: C. 模式匹配
解释: 模式匹配是指在主串 \(S\) 中查找子串 \(T\) 的首次出现位置。求子串操作是从串中截取特定部分，判断是否相等是比较两个字符串，连接则是将两个串合并。因此选择 C。

2. KMP 算法的特点是在模式匹配时指示主串的指针()

A. 不会变大
B. 不会变小
C. 都有可能
D. 无法判断

答案: B. 不会变小
解释: 在 KMP 算法中，当发生字符不匹配时，主串的指针不会回溯到前面的字符，而是保持在当前位置或向后移动。因此，主串的指针不会变小。

3. 设主串的长度为 \(n\)，子串的长度为 \(m\)，则简单的模式匹配算法的时间复杂度为() KMP 算法的时间复杂度为()。

A. \(O(m)\)
B. \(O(n)\)
C. \(O(mn)\)
D. \(O(m+n)\)

答案: C. \(O(mn)\)，D. \(O(m+n)\)
解释:

简单模式匹配算法的理论时间复杂度为 \(O(mn)\)，因为在最坏情况下可能需要比较主串的每个字符与子串的每个字符。
KMP 算法通过利用部分匹配的信息，可以将时间复杂度优化为 \(O(m+n)\)，因此选择 C 和 D。