C++中的字符串匹配：一种高效的算法

字符串匹配是指在一个较长的字符串中查找一个较短的字符串的位置，这是一个常见的编程问题，也是许多应用程序的基础，比如文本编辑器、搜索引擎、数据压缩等。在本文中，我们将介绍一种在 C ++ 中进行字符串匹配的高效算法，即 KMP 算法。

KMP 算法是由 Donald Knuth、Vaughan Pratt 和 James H. Morris 于 1977 年提出的，它的全称是 Knuth-Morris-Pratt 算法。KMP 算法的核心思想是利用已经匹配过的部分字符串来避免重复比较，从而提高匹配效率。具体来说，KMP 算法使用一个辅助数组（称为 next 数组）来记录每个位置之前的最长相同前缀后缀长度，这样当匹配失败时，可以根据 next 数组的值来移动模式串（较短的字符串），而不是从头开始比较。

KMP 算法的实现步骤如下：

1. 首先，根据模式串计算出 next 数组，这可以通过一个循环来完成，时间复杂度为 O(m)，其中 m 是模式串的长度。
2. 然后，从左到右遍历主串（较长的字符串），用两个指针 i 和 j 分别指向主串和模式串的当前位置，初始时 i 和 j 都为 0。
3. 如果主串和模式串的当前字符相同，那么 i 和 j 都加一，继续比较下一个字符。
4. 如果主串和模式串的当前字符不同，那么根据 next 数组的值来移动模式串，即令 j =next[j]，如果 j 变为 -1，那么 i 加一，j 变为 0，重新开始比较。
5. 重复步骤 3 和 4，直到主串或模式串遍历完毕。
6. 如果模式串遍历完毕，那么说明匹配成功，返回 i - j 作为匹配位置；如果主串遍历完毕，那么说明匹配失败，返回 -1。

为了更好地理解 KMP 算法的过程，我们给出一个示例代码：

#include 
#include 
#include 
using namespace std;


// 计算 next 数组
vector getNext(string pattern) {int m = pattern.size();
vector next(m, -1); // 初始化为 -1
int i = 0, j = -1; // i 表示后缀末尾位置，j 表示前缀末尾位置
while (i  next = getNext(pattern); // 计算 next 数组
int i = 0, j = 0; // i 表示主串当前位置，j 表示模式串当前位置
while (i 

输出结果为：

The position of pattern in text is: 2

可以看到，KMP 算法可以在 O(n+m) 的时间内找到模式串在主串中的位置，而不需要进行多余的比较。KMP 算法是一种经典的字符串匹配算法，值得学习和掌握。