现有一个文本串s[n]和模式串p[m]，模式匹配是指寻找文本串s中与模式串p相同的子串。
朴素模式匹配时间复杂度为$O(n*m)$，因此需要KMP模式匹配，时间复杂度为$O(n+m)$。
KMP模式匹配要先求next[m]数组，next数组的定义有很多种，不同的定义有不同的求法，这里选用一个笔者觉得最容易理解、代码最简洁的定义，推荐使用。
next[i] = j表示p[0...i]的前缀p[0...j]与后缀p[i-j...i]相同（前后缀和串本身不能等长）且是最大前后缀（即p[0...j+1]和p[i-j-1...i]不再相同，或者j+1等于i不再是前后缀）。如果没有前后缀相同，next[i] = -1。也就是说，next[i]记录p[0...i]的最长相同前后缀中的前缀的最后一位下标。
next[0] = -1;
for (int i = 1, j = -1; i < m; i++) {
while (j >= 0 && p[j+1] != p[i]) j = next[j];
if (p[j+1] == p[i]) j++;
next[i] = j;
}
KMP模式匹配中，由于next数组的存在，p[j+1]与s[i]匹配失败时，遍历文本串s的指针i不需要回退，遍历模式串p的指针j只需要回退到next[j]即可。
当匹配到p[j+1]和s[i]时，s[i-1-k...i-1]与p[j-k...j]相同，而根据next数组，p[j-k...j]又与p[0...k]相同，因此s[i-1-k...i-1]与p[0...k]相同。此时若匹配失败，保持i不动，j回退到k即可（k即为next[j]）。
for (int i = 0, j = -1; i < n; i++) {
while (j >= 0 && p[j+1] != s[i]) j = next[j];
if (p[j+1] == s[i]) j++;
if (j == m-1) {
// 匹配成功后的操作
j = next[j];
}
}
注解：求next数组的代码与KMP模式匹配的代码相近，不过求next数组时，i从1开始，KMP模式匹配时，i从0开始。