---
title: KMP
tags:
  - concept
  - data-structure-and-algorithm
  - string
  - joplin
type: concept
source_type: reconstructed
created: 2026-04-22
updated: 2026-04-22
---

# KMP

> [!abstract]
> KMP 是字符串模式匹配算法，核心思想是在失配时利用模式串自身的前后缀信息，避免主串指针回退。

## 核心机制

- 预处理模式串得到 `next` 或 `nextVal`
- 匹配失配时调整模式串位置
- 主串指针不必重新回到已比较过的位置

## 为什么重要

- 它体现了“利用已有结构信息减少重复比较”的典型算法思想。
- 是串匹配中的高频基础概念。

## 易错点

- `next` 不是“下一个字符下标”，而是失配后模式串该跳到的位置依据。
- 重点在理解前后缀关系，不在死背模板。

## 来源

- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/9.串.md]]

## 相关页面

- [[线性结构]]