KMP算法详解与C++实现

"KMP算法，一种用于字符串匹配的高效算法，通过构建部分匹配表避免不必要的比较，提高效率。本文将介绍KMP算法原理及C++实现。" KMP算法，由Knuth、Morris和Pratt三位学者提出，是字符串匹配领域中的一种经典算法，相较于朴素的字符串匹配算法，KMP具有更高的效率，尤其适用于处理大规模文本。其核心思想在于减少重复比较，避免在不匹配时简单地将模式串右移一位，而是根据预计算的部分匹配表（或失配函数）确定模式串应移动的距离，从而避免无效的比较。 **KMP算法的两个主要步骤：** 1. **构建部分匹配表：** 部分匹配表记录了模式串中每个位置上最长的公共前后缀的长度。例如，对于模式串"ABABC"，部分匹配表为[0, 0, 1, 2, 0]，表示在不匹配时，可以跳过对应数量的字符。构建这部分匹配表是KMP算法的关键，通常通过动态规划的方式实现。 ```cpp std::vector<int> buildPartialMatchTable(const std::string& pattern) { int m = pattern.size(); std::vector<int> table(m, 0); int len = 0; // 当前匹配的前缀长度 int i = 1; while (i < m) { if (pattern[i] == pattern[len]) { len++; table[i] = len; i++; } else { if (len != 0) { len = table[len - 1]; } else { table[i] = 0; i++; } } } return table; } ``` 2. **在文本中搜索匹配：** 在文本串中，使用部分匹配表指导模式串的移动。当遇到不匹配时，不是简单地将模式串向右移动一位，而是根据部分匹配表中的值移动相应的步数，继续匹配。这一过程通常使用两个指针，一个指向文本串，一个指向模式串，通过迭代和调整这两个指针的位置来完成匹配。 ```cpp int KMPMatch(const std::string& text, const std::string& pattern, const std::vector<int>& table) { int n = text.size(), m = pattern.size(); int j = 0; // 模式串指针 for (int i = 0; i < n; i++) { if (text[i] == pattern[j]) { j++; } if (j == m) { // 成功匹配 return i - m + 1; } else if (j > 0) { j = table[j - 1]; // 根据部分匹配表调整 } } return -1; // 未找到匹配 } ``` 通过上述步骤，KMP算法能够在处理大量文本时展现出其优越的性能。它的平均时间复杂度为O(n)，最坏情况下为O(n + m)，其中n是文本串的长度，m是模式串的长度。这使得KMP算法成为字符串匹配问题的一个有效解决方案。