# 4、串

## 一、简单模式匹配

时间复杂度：O(mn)

## 二、KMP算法

时间复杂度：O(m+n)

### 求next数组

1. 求PM表：前缀与后缀并集中最长的子串的长度
2. 将PM表右移一位，首位补-1
3. 视情况+1
4. j从1开始

{% hint style="info" %}
例：设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功为止，进行的单个字符比较次数是多少次？

* **求NEXT数组**

"a"：0

"ab"：0

"aba"：1

"abaa"：1

"abaab"：2

"abaabc"：0

右移补-1，得：

<img src="https://2472502332-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUddTfPz1UQGspJpAxLN6%2Fuploads%2Fgit-blob-d7196b82e51422992644778910fd783067a48a0f%2FKMP-NEXT.png?alt=media" alt="" data-size="original">

* **匹配**
  * 第一趟
    * T\[5]与S\[5]匹配失败
    * NEXT\[5]=2
    * 从T\[5]与S\[2]开始继续匹配
  * 第二趟
    * 匹配成功
* 共计10次
  {% endhint %}

### 求nextval数组

1. 先求next数组
2. 对于每一位，对比其next数组index对应的文本
3. 若一样，将那一位的值赋值给当前；若不一样，则保留不变


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aye10032.gitbook.io/data-structure/4-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.