模式匹配

字符串模式匹配是计算机科学中的基础问题，主要是在一个主字符串中查找一个子字符串模式。

简单模式匹配算法

简单模式匹配算法通常指的是暴力方法（或称为朴素算法），其基本思想是逐个检查主字符串的每一个位置是否开始与子字符串匹配。

算法描述：

1. 从主字符串的第一个字符开始匹配。
2. 如果第一个字符匹配，那么匹配下一个字符，依此类推。
3. 如果在任何时刻字符不匹配，重新从主字符串的下一个字符开始匹配。
4. 如果子字符串完全匹配，返回主字符串中的开始位置。
5. 如果到达主字符串的末尾都没有完全匹配的子字符串，则返回-1。

int simplePatternMatching(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    // 如果主字符串的长度小于模式字符串的长度，直接返回-1
    if (m < n) return -1;

    for (int i = 0; i <= m - n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (mainStr[i + j] != pattern[j]) {
                break;
            }
        }
        // 如果j等于模式串的长度，说明已经找到匹配
        if (j == n) return i;
    }
    return -1;  // 没有找到匹配
}

这个简单模式匹配算法的时间复杂度是 $O(mn)$ ，其中 $m$ 是主字符串的长度， $n$ 是模式字符串的长度。

KMP算法

与简单模式匹配算法不同，KMP算法在发现不匹配的字符时能够避免不必要的比较，从而提高效率。

前后缀

简单模式匹配时间复杂度过高，因为每一次匹配失败都得从下一个位置重新开始。这就没有充分应用模式串的特性，比如对于字符串 abcdabc，我们可以发现：

• 其前缀包含a, ab, abc, abcd等
• 起后缀包含c, bc, abc, dabc等

abc是在其前缀和后缀中都包含的部分，在字符串匹配时，我们可以充分利用该信息，匹配失败时，我们可以不用从下一个位置开始，而是从模式串内部的某个位置开始。

KMP算法就是基于这个思想，其核心是一个称为“部分匹配表”或“前缀函数”的辅助数组（通常称为next数组），该数组用于确定当模式串与主串不匹配时应该如何有效地移动模式串。

算法描述

1. 构建部分匹配表（next 数组）：next[i] 表示：当模式串在第 i 位匹配失败时，下一次应该跳到的模式串位置。
2. 不断进行模式匹配，直到匹配成功或主串结束。

next数组计算

如果模式串为pattern，用通俗的话来说，next[k]就是第 k 个字符的前缀字符串 pattern[0:k-1]（pattern的前k个字符构成的子串，不包含当前字符）的最长相同前缀和后缀的长度。

以 ababac 字符串为例，可以得到以下的 next 数组：

一般而言，next 数组中的第一个元素被设置为 -1（因为第一个字符不存在前缀子串）。

以 c 字符为例，我们需要计算 next[5]，所以需要统计 c 的前缀字符串 ababa 的最长相同前缀和后缀的长度，可以观察到，最长的相同前缀和后缀为 aba，长度为 3，所以 next[5] = 3。

使用next调整位置

用i表示主串当前下标，用j表示模式串当前下标：

• 如果main[i] == pattern[j]，将i和j向后向后移动一位。
• 如果main[i] != pattern[j]：
  • 如果j == 0，将i向后移动一位。
  • 如果j != 0，将j移动到next[j]。

以下图为例，说明主串 “ababcabcabababd” 和 模式串 “ababd” 的匹配过程。

算法实现

算法实现了解即可，考试基本不会考察 kmp 算法实现，只要能够熟练地在纸上模拟 kmp 算法流程即可。

void computeNextArray(const char* pattern, int m, int* next) {
    int len = 0;
    next[0] = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
}

int KMP(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    int next[n];
    computeNextArray(pattern, n, next);

    int i = 0, j = 0;
    while (i < m) {
        if (pattern[j] == mainStr[i]) {
            i++;
            j++;
        }

        if (j == n) {
            return i - j;
        } else if (i < m && pattern[j] != mainStr[i]) {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
    }

    return -1; // 没有找到匹配
}

修正后的next数组

其实上述内容就是 kmp 算法的核心了，当然有时候也会涉及到这样一个概念：修正后的 next 数组。

这个概念其实来源于早期教材（特别是严蔚敏的《数据结构》），修正后的 next 数组常称作 nextval 数组，其目的是避免某些情况下的冗余匹配。

nextval 数组是为了修正 next 数组存在的以下问题：

在某些情况下，即使知道跳转到 next[i]，但 pattern[i] == pattern[next[i]]，跳过去会导致再次比较重复的字符，这是冗余的。

所以 nextval 的构建规则如下：

• 如果 pattern[i] == pattern[next[i]] → 则 nextval[i] = nextval[next[i]]
• 否则 → nextval[i] = next[i]

以字符串 ababaa 为例，我们首先可以计算出其 next 数组：

然后计算出 nextval 数组：

• nextval[0] = -1
• nextval[1] = 0
• nextval[2] = 0
• pattern[3] = b, pattern[next[3]] = pattern[1] = b, 相等，优化：nextval[3] = nextval[1] = 0
• pattern[4] = a, pattern[2] = a, 相等，优化：nextval[4] = nextval[2] = 0
• nextval[5] = 3（pattern[5] = a, pattern[3] = b，不相等，保留原值）

其实 kmp 的现代实现中一般使用 next 数组就足够了， nextval 主要是优化了极少数情况下的性能，特别是在大量重复字符的模式串里效果明显。