KMP

1. 简介

KMP 算法是一种优秀的字符串模式匹配算法，相对于暴力匹配方法来说，其改进在于：每当一趟匹配过程出现字符比较不相等时，不需回溯主串的 $i$ 指针，而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后（即回溯模式串的 $j$ 指针），继续进行比较。

2. 实现

• 设模式串为 $p_1 p_2 \cdots p_m$，主串为 $s_1 s_2 \cdots s_n$。

• 定义失配数组 $next[j]$ 表示当模式串中第 $j$ 个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的模式串字符的位置。

1. 假设从主串第 $pos$ 个字符开始和模式串匹配，此时主串中第 $i(pos \leq i)$ 个字符和模式串的第 $j$ 个字符比较，且 $s_i \ne p_j$，说明从主串第 $pos$ 个字符开始匹配无法找到模式串子串，因此需要将 $pos$ 向右「滑动」（即增大主串开始匹配字符的位置）。
2. 而增大主串开始匹配字符的位置可以通过将模式串向右「滑动」实现。如果此时存在最大的 $k$ 使得 $p_0 \cdots p_{k-1} = p_{j-k} \cdots p_{j-1}$ 且 $p_k \ne p_j$，则可以将模式串向右「滑动」使得模式串第 $k$ 个字符对应到第 $j$ 个字符，即模式串整体向右滑动了 $j-k$ 个字符。

• 设 $k = max\{u | 0 \lt u \lt j \bigwedge p_0 \cdots p_{u-1} = p_{j-u} \cdots p_{j-1}\}$，则失配数组的计算公式如下：

$$\begin{array}{c} next[j] = \begin{cases} -1 & j = 0 \\ k & if \ p_{k} \ne p_{j} \\ next[k] & if \ p_{k} = p_{j} \end{cases} \end{array}$$

计算失配数组时间复杂度 $O(m)$，主串与模式串匹配时间复杂度 $O(n)$，故 KMP 算法总的时间复杂度为 $O(n+m)$ 。

3. 模板

#include <bits/stdc++.h>
using namespace std;

#ifndef _KMP_
#define _KMP_
#define ll int
#define MAXN 1000005
#define MAXM 1000005

// KMP 算法
struct KMP {
    // 失配数组
    // next[j] 表示当模式中第 j 个字符与主串字符失配时
    // 模式串中失配位置需要滑动到的位置
    ll next[MAXM];   
    vector <ll> match;          
    KMP() {}
    // 计算失配数组
    void getNext(char *pattern, ll m) {
        // pattern 模式串
        next[0] = -1;
        ll i = 0, j = -1;
        while(i < m) {
            if(!(~j) || pattern[i] == pattern[j]) {
                ++i, ++j;
                if(pattern[i] != pattern[j])    next[i] = j;
                else    next[i] = next[j];
            } else {
                j = next[j];
            }
        }
    }
    // 计算模式串在主串中第 pos 个字符后出现首个匹配的首位置
    ll getIndex(ll pos, char *main, ll n, char *pattern, ll m) {
        ll i = pos, j = 0;
        while(i < n && j < m) {
            if(!(~j) || main[i] == pattern[j]) {
                ++i, ++j;
            } else {
                j = next[j];
            }
        }
        if(j < m) {
            return -1;
        }
        return i - m;
    }
    // 计算模式串在主串中所有匹配的首位置
    void getIndexs(char *main, ll n, char *pattern, ll m) {
        ll i = 0, j = 0;
        while(i < n) {
            if(!(~j) || main[i] == pattern[j]) {
                ++i, ++j;
                if(j == m) {
                    j = next[j];
                    match.push_back(i-m);
                }
            } else {
                j = next[j];
            }
        }
    }
};
#endif