本笔记内容来源于算法基础课

KMP

s[N]是原字符串
p[M]是模板串
字符串下标均从1开始，但i从1开始，j从0开始

暴力做法

从原字符串的i开始匹配，判端是否与模板串相同

for (int i = 1; i <= n; i++) {
    bool flag = true;
    for (int j = 0; j <= m; j++) {
        if (s[i + j] != p[j]) {
            flag = false;
            break
        }
    }
}

考虑优化

对于从[l , i - 1]区间元素与模板串相同，i元素与模板串不同
在下次匹配时可以利用信息

在下次匹配时，模板串可以直接向右移动多少开始新的匹配

即图中的红色虚线框的为相同的子串

而新的开始匹配的串与模板串中子串相等，因此模板串中后缀和前缀的最长相等即为可以移动的最短距离

考虑以j结束的最长的相等前缀next[j]，因为下一次匹配j是从0开始的，因此相等的边界下标为next[j]

注意下标始终错一位

移动后，再判断s[i]和p[j + 1]，若不相同，则递归移动

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 匹配
for (int i = 1, j = 0; i <= n; i++) {
    while (j > 0 && s[i] != p[j + 1]) j = ne[j]; // p与s比较，无法向后移动，则递归
    if (s[i] == p[j + 1]) j++; // 相同则移动边界
    if (j == m) {
        j = ne[j];
        // 匹配后逻辑
    }
}

next[i] = j代表以1开始长度为j的前缀等于以i结束长度为j的后缀

p[1 ,j] = p[i -j + 1, i]

求next，不断与i结束的自身匹配，从而获得长度相等的前缀和后缀

注意next[1] = 0 因此从2开始求

// 求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i++) {
    while (j > 0 && p[i] != p[j + 1]) j = ne[j]; // p与p比较，无法向后移动则递归
    if (p[i] == p[j + 1]) j++;  // 相同则移动边界
    ne[i] = j; // 前缀与以i结尾的后缀相同的长度为 j - 1 + 1 = j
}