贤鱼的刷题日常-P3375 【模板】KMP 字符串匹配

**贤鱼的刷题日常**

### P3375 KMP 字符串匹配####问题描述给定两个字符串 `s` 和 `p`,其中 `p` 是模式串，要求在 `s` 中找到所有匹配 `p` 的子串，并返回这些子串的起始索引。

#### 示例* 输入:`s = "ababababab"、`p = "abab"`
输出：[0,3,6]
* 输入:`s = "hello world"`、`p = "world"`
输出：[7]

#### 思路KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，主要用于解决模式串在长文本中查找的问题。该算法通过预处理模式串来计算最大前缀后缀匹配（PREF/SUFF）值，从而减少不必要的比较。

#### KMP 算法步骤1. **预处理模式串**：计算模式串 `p` 的最大前缀后缀匹配值，存储在数组 `pref` 中。
2. **主循环**：从文本 `s` 开始逐一比较字符，与模式串 `p` 进行匹配。每当发现不匹配时，根据 `pref` 值跳过不必要的比较，以减少时间复杂度。

#### KMP 算法实现

cpp#include <iostream>
#include <vector>

// KMP算法预处理函数std::vector<int> kmpPreprocess(const std::string& p) {
 int n = p.size();
 std::vector<int> pref(n,0);
 // 计算最大前缀后缀匹配值 for (int i =1; i < n; ++i) {
 int j = pref[i -1];
 while (j >0 && p[j] != p[i]) {
 j = pref[j -1];
 }
 if (p[j] == p[i]) {
 pref[i] = j +1;
 } else {
 pref[i] =0;
 }
 }
 return pref;
}

// KMP算法主函数std::vector<int> kmpSearch(const std::string& s, const std::string& p) {
 int m = s.size();
 int n = p.size();
 // 预处理模式串 auto pref = kmpPreprocess(p);
 // 主循环 std::vector<int> indices;
 for (int i =0; i <= m - n; ++i) {
 int j =0;
 while (j < n && s[i + j] == p[j]) {
 j++;
 }
 if (j == n) {
 // 匹配成功，记录索引 indices.push_back(i);
 // 根据pref值跳过不必要的比较 i += pref[j -1];
 } else {
 // 不匹配，直接移动到下一个位置 i++;
 }
 }
 return indices;
}

int main() {
 std::string s = "ababababab";
 std::string p = "abab";
 auto indices = kmpSearch(s, p);
 // 输出匹配结果 for (const auto& index : indices) {
 std::cout << index << " ";
 }
 return0;
}

#### KMP 算法分析* **时间复杂度**：KMP算法的时间复杂度为 O(m + n)，其中 m 是文本长度，n 是模式串长度。
* **空间复杂度**：KMP算法的空间复杂度为 O(n)，用于存储最大前缀后缀匹配值。

#### KMP 算法优点* **高效性**：KMP算法比暴力匹配法更高效，尤其是在模式串长且文本长度较大的情况下。
* **简单性**：KMP算法的实现相对简单，不需要复杂的数据结构或算法。

#### KMP 算法缺点* **预处理时间**：KMP算法需要额外的预处理时间来计算最大前缀后缀匹配值。
* **空间需求**：KMP算法需要额外的空间来存储最大前缀后缀匹配值。

#### KMP 算法应用* **文本搜索**：KMP算法广泛用于文本搜索，例如在编辑器或浏览器中查找特定字符串。
* **模式识别**：KMP算法也可以用于模式识别，例如在图像处理或信号处理中检测特定模式。

#### KMP 算法总结KMP算法是一种高效的字符串匹配算法，主要用于解决模式串在长文本中查找的问题。该算法通过预处理模式串来计算最大前缀后缀匹配值，从而减少不必要的比较。虽然 KMP 算法有其优点，但也存在一些缺点，如预处理时间和空间需求。