> For the complete documentation index, see [llms.txt](https://dipo.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dipo.gitbook.io/leetcode/implement-strstr/kmpsuan-fa.md).

# KMP算法

## 判断字符串str1是否含有子串str2

## 关键是实现next数组

### next数组就是针对str2串中每个字符前的子串中存在的前缀与后缀匹配的最长长度

* "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
* 假设str2为“abababca”。
  * j=0，字符str2\[j]=a，a前没有字符串，默认为next\[0]=-1; 
  * j=1，字符str2\[j]=b，b前子串为“a”，前后缀不存在，默认为next\[1]=0; 
  * j=2，字符str2\[j]=a，a前子串为“ab”，前后缀不存在相等，则next\[2]=0; 
  * j=3，字符str2\[j]=b，b前子串为“aba”，前后缀最大相等为a，则next\[3]=1; 
  * 以此类推next\[9]=\[-1,0,0,1,2,3,4,0]


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://dipo.gitbook.io/leetcode/implement-strstr/kmpsuan-fa.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.