> For the complete documentation index, see [llms.txt](https://aye10032.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aye10032.gitbook.io/data-structure/4-chuan.md).

# 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. 若一样，将那一位的值赋值给当前；若不一样，则保留不变