# KMP 算法的定义

$KMP$ 算法常用于在一个文本串 $S$ 内查找一个模式串 $P$ 出现的位置，算法流程如下：

假设现在文本串 $S$ 匹配到 $i$ 位置，模式串匹配到 $j$ 位置：

如果 j = -1 ，或者当前字符匹配成功（ s[i] == p[j] ），都令 i++, j++ ，然后继续匹配下一个字符
如果 j != -1 ，并且当前字符匹配失败（ s[i] != p[j] ），则令 $i$ 不变， j = next[j] 。此操作意味着当匹配失败时，模式串 $P$ 相对于文本串 $S$ 向右移动了 j - next[j] 位

# next 数组的含义

表示当前字符之前的字符串中，有多大长度的相同前后缀。例如如果 next[j] = k ，则代表 $j$ 之前的字符串中有最大长度为 $k$ 的相同前后缀
此也意味着在某个字符匹配失败时，该字符对应的 $next$ 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到 next[j] 的位置）
如果 next[j] 等于 $0$ 或 $-1$ ，则跳到模式串的开头字符，若 next[j] = k 且 k > 0 ，则代表下次匹配跳到 $j$ 之前的某个字符，而不是跳到开头，且具体跳过了 $k$ 个字符

# KMP 算法的步骤

# 寻找前缀后缀最长公共元素长度

对于 p = p0 p1 ... pj-1 pj ，寻找模式串 $P$ 中长度最大且相等的前缀和后缀，如果存在 $P_0,~P_1,~...,~P_{k-1}~=~P_{j-k},~=P_{j-k},~P_{j-k+1},~...,~P_j$ ，那么在包含 $P_j$ 的模式串中有最大程度为 $k+1$ 的相同前缀后缀
例如，如果给定的模式串 $P$ 是 $abab$ ，那么它的各个字串的前缀后缀公共元素的最大长度为：

模式串	$a$	$b$	$a$	$b$
最大前缀后缀公共元素长度	$0$	$0$	$1$	$2$

# 求 next 数组

$next$ 数组考虑的是除当前字符外的最长相同前后缀串长度，所以求得各个前缀后缀的公共元素最大长度后，只要稍作变形即可，将步骤一中求得的值整体右移一位，初始值赋为 $-1$

模式串	$a$	$b$	$a$	$b$
$next$ 数组	$-1$	$0$	$0$	$1$

next[i] 表示第 $i$ 个字符前，有长度为 next[i] 的相同前缀后缀字符串

# 根据 $next$ 进行模式匹配

如果匹配失败，模式串向右移动的位数为： j - next[j]
换言之，当模式串的后缀 $P_{j-k},~P_{j-k+1},~...,~P_{j-1}$ 跟文本串 $S_{i-k},~S_{i-k+1},~...,~S_{i-1}$ 匹配成功，但 $P_j$ 和 $S_i$ 匹配失败时，因为 next[j] = k ，相当于在不包含 $P_j$ 的模式串中有最大长度为 $k$ 的相同前缀后缀
即 $P_0,~P_1,~...,~P_{k-1}~=~P_{j-k},~=P_{j-k},~P_{j-k+1},~...,~P_j$ ，故令 j = next[j] ，从而让模式串右移 j - next[j] 位，使得模式串的前缀 $P_0,P_1,~...,~P_{k-1}$ 对应着文本串 $S_{i-k},~S_{i-k+1},~...,~S_{i-1}$ ，然后继续让 $P_k$ 和 $S_i$ 匹配

# 递推计算 next 数组

# 再次介绍 next 数组的含义

如果对于 $k$ ，已有 $P_0,~P_1,~P_{k-1}~=~P_{j-k},~P_{j-k+1},~...,~P_{j-1}$ 相当于 next[j] = k 。
这意味着什么呢？究其本质， next[j] = k 代表 $P_0~\to~P_{j-1}$ 的模式字串中，有长度为 $k$ 的相同前缀和后缀。
有了这个 $next$ 数组，在 KMP 匹配中，当模式串中 $j$ 处的字符继续跟文本串匹配失败时，下一步用 $next[j]$ 处的字符继续跟文本串匹配，相当于模式串向右移动 j - next[j] 位

已知 $next[0,~...,~j]$ ，如何求出 $next[j~+~1]$ 呢？
- 对于 $P$ $P$ 的前 $j+1$ $j + 1$ 个序列字符：
  - 如果 p[k] == p[j] ，则 next[j + 1] = next[j] + 1 = k + 1 。
  - 如果 p[k] != p[j] ，如果此时的 p[next[k]] == p[j] ，则 next[j + 1 = next[k] + 1 ，否则继续递归前缀索引 k = next[k] ，而后重复此过程。相当于在字符 $P_{j+1}$ 之前不存在长度为 $k+1$ 的前缀 $P_0,~P_1,~...,~P_k$ 跟后缀 $P_{j-k},~P_{j-k+1},~...,~P_{j-1},~P_j$ 相等。那么是否可能存在另一个值 $t+1~\le~k+1$ ，使得长度更小的前缀 $P_0,~P_1,~...,~P_{t-1},~P_t$ 等于长度更小的后缀 $P_{j-1},~P_{j-t+1},~...,~P_{j-1},~P_j$ 呢？如果存在，那这个 $t+1$ 便是 $next[j+1]$ 的值，此相当于利用已经求得的 $next$ 数组（ $next[0,~...,~k,~...,~j]$ ）进行 $P$ 串前缀跟 $P$ 串后缀的匹配。

# 如何理解上面这个抽象的描述

情况 1： $P_k~=~P_j~$

模式串	$\color{red}A$	$\color{red}B$	$\color{green}C$	$D$	$\color{red}A$	$\color{red}B$	$\color{green}C$	$E$
相同前后缀长度	$0$	$0$	$0$	$0$	$1$	$2$	$3$	$0$
$next$ 值	$-1$	$0$	$0$	$0$	$0$	$1$	$2$	$?$
索引	$P_0$	P_	$P_k$	P_	P_	P_	$P_j$	P_

因为 $P_k~=~P_j~=~'C'$ ，所以 next[j + 1] = next[j] + 1 = k + 1 （可以看出 next[j + 1] = 3 ）
代表字符 $E$ 前的模式串中，有长度为 $k+1$ 的相同前后缀字串

情况 2： $P_k~\not=~P_j$

模式串	$\color{red}A$	$\color{red}B$	$\color{green}C$	$D$	$\color{red}A$	$\color{red}B$	$\color{blue}D$	$E$
相同前后缀长度	$0$	$0$	$0$	$0$	$1$	$2$	$0$	$0$
$next$ 值	$-1$	$0$	$0$	$0$	$0$	$1$	$2$	$?$
索引	$P_0$	P_	$\color{green}P_k$	P_	P_	P_	$\color{blue}P_j$

$P_k~\not=~P_j$ 说明 $P_0,~P_{k-1},~P_k~\not=~P_{j-k},~P_{j-1},~P_j$ 。换言之，字符 $E$ 前能有多大长度的相同前缀后缀呢？
很明显，因为 $'C'~\not=~'D'$ ，即字符 $E$ 前没有长度为 $k+1$ 的相同前缀后缀，也就不能简单地令 next[j + 1] = next[j] + 1
所以，我们只能寻找长度更短的相同前缀后缀
结合上表来看，如果能在前缀 $P_0,~P_{k-1},~P_k$ 中不断递归前缀索引 k' = next[k] ，找到一个字符 $P_{k'}$ 也为 $'D'$ ，代表 $P_{k'}~=~P_j$ ，且满足于 $P_0,~P_{k'-1},~P_{k'}~\not=~P_{j-k'},~P_{j-1},~P_j$ ，则最大相同的前缀后缀长度为 $k'-1$ ，从而 next[j + 1] = k' + 1 = next[k'] + 1
如果没有这样的 $k'$ 满足 $P_{k'}~=~'D'$ 的话，则代表没有相同的前缀后缀， next[j + 1] = 0

# 为何递归 k = next_k 就能找到长度更短的前缀后缀？

这归根到 $next$ 数组的含义。我们拿前缀 $P_0,~P_{k-1},~P_k$ 和后缀 $P_{j-k},~P_{j-1},~P_j$ 匹配，如果 $P_k~ \not= P_j$ ，下一步就是用 $p[next[k]]$ 去和 $P_j$ 匹配，如果还是不匹配，则需要寻找长度更短的相同前缀后缀，即用 $p[next[next[k]]]$ 去和 $P_j$ 匹配。此过程相当于模式串的自我匹配，所以不断递归 k = next[k] ，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。

# 代码

C++

#include <stdio.h>
#include <string.h>

void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat); // 模式字符串的长度
    int N = strlen(txt); // 目标字符串的长度

    // 创建next数组，next[i]表示pat[0..i]的最长的相同的前缀和后缀的长度
    int next[M];

    // 计算next数组
    computeNextArray(pat, M, next);

    int i = 0; // txt的索引，从头开始
    int j = 0; // pat的索引，从头开始

    /*  查询串
    I   idx         0   1   2   3   4   5   6   7   8   9   10  11
                    A   B   A   B   A   B   C   A   B   A   B   C
                                    
    */
    
    /*  模式串
        idx         0   1   2   3   4  
        string:     A   B   A   B   C 
        next:       0   0   1   2   0
    */
    
    // 遍历目标字符串
    while (i < N) {
        if (pat[j] == txt[i]) {
            // 如果当前字符匹配
            i++; // 移动到目标字符串的下一个字符
            j++; // 移动到模式字符串的下一个字符
        }

        if (j == M) {
            // 如果找到了整个模式字符串
            printf("Found pattern at index %d\n", i - j); // 打印起始位置
            j = next[j - 1]; // 更新j为next[j-1]，继续搜索
        }
        else if (i < N && pat[j] != txt[i]) {
            // 如果当前字符不匹配
            if (j != 0) {
                j = next[j - 1]; // 更新j为next[j-1]，尝试下一匹配
            } else {
                i++; // 如果j为0，移动到目标字符串的下一个字符
            }
        }
    }
}

void computeNextArray(char* pat, int M, int* next) {
    int len = 0; // 当前最长相同前缀和后缀的长度
    next[0] = 0; // next[0]总是0，第一个字符没有前缀和后缀
    int i = 1; // 从模式字符串的第二个字符开始

    // 遍历整个模式字符串，计算next数组
    while (i < M) {
        if (pat[i] == pat[len]) {
            // 如果当前字符与len对应的字符相同
            len++; // 当前最长相同前缀和后缀的长度加1
            next[i] = len; // 将长度值赋给next数组的当前索引
            i++; // 移动到下一个字符
        } else {
            // 如果当前字符与len对应的字符不相同
            if (len != 0) {
                // 如果len不为0，更新len为next[len - 1]
                len = next[len - 1];
                // 这样做是为了找到一个较短的前缀，使得该前缀可能与当前字符匹配
            } else {
                // 如果len为0，直接将next[i]设置为0
                next[i] = 0;
                i++; // 移动到下一个字符
            }
        }
    }
}

int main() {
    char txt[] = "ABABABAB";
    char pat[] = "AB";
    KMPSearch(pat, txt);
    return 0;
}

C++

#include <stdio.h>
#include <string.h>

const int N = 1e6 + 10;

char s[N], p[N];
int next[N];

void creatNext(char *s, int *next) {
    next[0] = 0;
    int len = 0, i = 1;

    while(i < strlen(s)) {
        if(s[i] == s[len])
            next[i++] = ++len;
        else {
            if(len != 0)
                len = next[len - 1];
            else
                next[i++] = 0;
        }
    }
}

void kmp(char *s, char *p) {
    int i = 0, j = 0, n = strlen(s), m = strlen(p);

    while(i < n) {
        if(s[i] == p[j])
            i++, j++;
        
        if(j == m) {
            printf("%d ", i - j);
            j = next[j - 1];
        }
        else if(i < n && s[i] != p[j]) {
            if(j != 0)
                j = next[j - 1];
            else i++;
        }
    }
}

int main() {
    scanf("%s%s", s, p);
    creatNext(p, next);

    kmp(s, p);
}