先看一下KMP核心的next数组的操作：
nex[0] = -1;
for (i = 1; i <= len; i++)
{
while (j >= 0 && st[j + 1] != st[i]) //不匹配回溯一个大规律
j = nex[j];
nex[i] = ++j; //经过上面的循环，要么j回到了0，要么已经重新回到了st[j+1]==st[i]可以继续匹配啦
}
如串a b a b a c
下标1 2 3 4 5 6
j 匹配 回溯 nex[1]=0
0 ([1]a!=[2]b) -1 2=0
0 ([1]a=[3]a) No 3=1
1 ([2]b=[4]b) No 4=2
2 ([3]a=[5]a) No 5=3
3 ([4]b!=[6]c) 2
2 ([2]b!=[6]c) -1 6=0
可以得到：
串 a b a b a c
下标 1 2 3 4 5 6
next数组 0 0 1 2 3 0
如当下标为5不匹配时，我们将直接回溯到下标[3-1]的[2]b上
下标为6不匹配时，我们将回溯到[1]a上从新开始
看一道例题——2021年广东工业大学第十五届文远知行杯程序设计竞赛-B题找山坡
链接：https://ac.nowcoder.com/acm/contest/13504/B
计算:
样例输入：
5
1 2 3 2 1
样例输出：
4 （ [5]1 - [1]1 = 4 ）
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn];
int nex[maxn];
int j = 0;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i++)
{
while (j && a[nex[j]] > a[i])
j--; //遇到a[i]变小，前推nex[j]，扩大区间
if (j && a[nex[j]] == a[i]) //匹配值等于a[i]时，取最大区间
ans = max(ans, i - nex[j]);
else
nex[++j] = i;
}
printf("%d\n", ans);
return 0;
}
如：
5
1 2 3 2 1
我们第一次匹配到的应该是[2]2 [4]2 ans=4-2=2
[5]1 < [4]2 nex[j]前推 [1]1 = [5]1 ans=4
看大佬写的题解，他们好像是一类问题，可以用单调栈/单调队列乱杀。待我学习补充..
原文：https://www.cnblogs.com/thx2199/p/14588988.html