kmp的神奇之处

$ kmp $ 想必大家都不陌生，这里先贴个模板hh

从０开始：

 for (int i = 1, j = 0; i < s2.length(); i++)
    {
        while (j && s2[i] != s2[j])
            j = ne[j - 1];
        if (s2[i] == s2[j]) j++;
        ne[i] = j;
    }
    for (int i = 0, j = 0; i < s1.length(); i++)
    {
        while (j && s1[i] != s2[j]) j = ne[j - 1];
        if (s1[i] == s2[j]) j++;
        if (j == s2.length())
            cout << i - s2.length() + 2 << '\n', j = ne[j - 1];
    }

对于从１开始：

for (int i = 2, j = 0; i <= m; i++)
{
    while (j && s2[i] != s2[j + 1])
        j = ne[j];
    if (s2[i] == s2[j + 1])
        j++;
    ne[i] = j;
}
for (int i = 1, j = 0; i <= n; i++)
{
    while (j && s1[i] != s2[j + 1])
        j = ne[j];
    if (s1[i] == s2[j + 1])
        j++;
    if (j == m - 1)
    {
        cout << i - m + 2 << endl;
        j = ne[j];
    }
}

这两者本质上没有什么区别，只不过是位置不同，当然，这只是字符串匹配，但是你知道吗？他还能做到这样一种事：两个数组，任意一段连续的区间，\(kmp\) 都能做到判断一个数组是否在这一段区间上整体大于等于或者整体小于等于，做法也是类似于上面的匹配模式，只是改了一下判断条件

这是题目

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> ne(2 * n + 1);
    vector<int> good(2 * n + 1);
    function<bool(int)> check;
    check = [&](int u) -> bool
    {
        if (2 * u - 1 > n) return false;
        for (int i = 1; i <= u; i++)
        {
            good[i] = i, good[2 * u - i] = i;
        }
        fill(ne.begin(), ne.end(), 0);
        for (int i = 2, j = 0; i <= 2 * u - 1; i++)
        {
            while (j && good[i] < good[j + 1]) j = ne[j];
            if (good[i] >= good[j + 1]) j++;
            ne[i] = j;
        }
        for (int i = 1, j = 0; i <= n; i++)
        {
            while (j && a[i] < good[j + 1]) j = ne[j];
            if (a[i] >= good[j + 1]) j++;
            if (j == 2 * u - 1) return true;
        }
        return false;
    };
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}

此外，如果需要求出从一段字符串的后缀匹配前缀的所有长度的话，其匹配方式还要稍作改变，在一般的模式中，\(ne[i]\) 表示的是包括ｉ位置之前的所有字符串的匹配，而这样我们在求得过程中会进入死循环，所以要改变一下：

for (int i = 1, j = 0; i <  n; i++)
{
    while (j && s[i] != s[j]) j = ne[j];
    if (s[i] == s[j]) j++;
    ne[i + 1] = j;
}
for (int i =  n; i; i = ne[i])
    if (i <= n) ok[i]++;

这样就表示得是:从后缀得最后一个位置开始，他除了他自己以外能够匹配前缀得最长长度