C++ KMP算法详解：高效字符串匹配利器

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。相比于朴素的字符串匹配算法，KMP算法能够利用已经匹配的信息避免重复比较，从而提高匹配效率。

1. KMP算法原理

KMP算法的核心思想是利用模式串自身的特性来加速匹配过程。具体来说，KMP算法会预先计算模式串的最长公共前缀后缀数组（LPS数组），该数组存储了模式串每个位置的前缀子串与模式串本身的最长公共前缀的长度。

在匹配过程中，当遇到失配的情况时，KMP算法会根据LPS数组的信息将模式串尽可能多地向右移动，以避免不必要的比较。

2. KMP算法步骤

KMP算法的实现主要分为两个步骤：

2.1 预处理模式串，构建LPS数组

遍历模式串，逐个计算每个位置的LPS值。- LPS[i] 表示模式串中以 i 为结尾的前缀子串与模式串本身的最长公共前缀的长度。

2.2 匹配过程

初始化两个指针 i 和 j，分别指向主串和模式串的起始位置。- 循环比较主串和模式串的字符，直到找到匹配或者遍历完主串。 - 如果当前字符匹配 (text[i] == pattern[j])，则将两个指针都向后移动一位 (i++, j++)。 - 如果当前字符不匹配 (text[i] != pattern[j])： - 如果 j > 0，则根据 LPS 数组将模式串向右移动，并将 j 更新为 LPS[j - 1]； - 如果 j = 0，则将主串指针 i 向后移动一位 (i++)。- 如果匹配成功 (j == pattern.length())，则返回匹配的起始位置 i - j。

3. C++ 代码实现c++#include #include

using namespace std;

// 计算模式串的 LPS 数组vector buildLPS(string pattern) { int m = pattern.size(); vector lps(m, 0); int len = 0; // 当前最长公共前缀的长度 lps[0] = 0; // 第一个位置的 LPS 值始终为 0 for (int i = 1; i < m; i++) { while (len > 0 && pattern[i] != pattern[len]) { len = lps[len - 1]; // 回溯到上一个可能匹配的位置 } if (pattern[i] == pattern[len]) { len++; } lps[i] = len; } return lps;}

// KMP 算法匹配过程int kmpSearch(string text, string pattern) { int n = text.size(); int m = pattern.size(); vector lps = buildLPS(pattern); int j = 0; // 模式串指针 for (int i = 0; i < n; i++) { while (j > 0 && text[i] != pattern[j]) { j = lps[j - 1]; // 根据 LPS 数组回溯 } if (text[i] == pattern[j]) { j++; } if (j == m) { // 匹配成功 return i - j; } } return -1; // 未找到匹配}

int main() { string text = 'ABABDABACDABABCABAB'; string pattern = 'ABABCABAB'; int index = kmpSearch(text, pattern); if (index != -1) { cout << '模式串在主串中的起始位置为：' << index << endl; } else { cout << '未找到匹配' << endl; } return 0;}

4. 总结

KMP算法是一种高效的字符串匹配算法，它通过预处理模式串和利用LPS数组的信息来避免不必要的比较，从而提高了匹配效率。KMP算法的时间复杂度为 O(n + m)，其中 n 为主串长度，m 为模式串长度。