KMP自用板子

KMP：一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己

题目描述

给定一个字符串 $S$，以及一个模式串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 $P$ 在字符串 $S$ 中多次作为子串出现。
求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式

第一行输入整数 $N$，表示模式串 $P$ 的长度。

第二行输入字符串 $P$。

第三行输入整数 $M$，表示字符串 $S$ 的长度。

第四行输入字符串 $S$。

输出格式

共一行，输出所有出现位置的起始下标（下标从 $0$ 开始计数），整数之间用空格隔开。

数据范围

$ 1≤N≤10^5 $

$ 1≤M≤10^6 $

输入样例：

3
aba
5
ababa

输出样例：

0 2

算法剖析

$next[i]本质:模式串前i个字符的最长的一对相等的前后缀size(＝该前缀末端index)[下标从1开始]$
$如$:”$abab$”, $size$=$2$

$每次循环开始的时候,j都=ne[i - 1]，下面分两种情况来讨论：$
$①.if\;\;p_{i}=p_{j+1}$
$\;\;\;\;\;\;\;\;\;\; ne[i] \gets ne[i - 1] + 1$
$②.if\;\;p_{i} \ne p_{j+1}$
$\;\;\;\;\;\;\;\;\;\; j \gets ne[j],再重新开始判断if\;(p_{i}=p_{j+1})$

// 求next数组过程:其实就是求最大前后缀长度，通过仿造下面KMP匹配的过程来求,可以将暴力求的o(n^2)复杂度降至o(n)
for (int i = 2, j = 0; i <= n; i++)           // 注意这里i得从2开始,因为默认ne[1]=0,如果这里i从1开始,很明显会导致ne[1]=1,最终代码会出现TLE
{
    while (j != 0 && p[i] != p[j + 1])  j = ne[j];   // 只要j没有退回起点,并且p[i]和p[j+1]不匹配,就可以通过next数组更新j
    if (p[i] == p[j + 1]) j++;   // 如果最终p[i]和p[j+1]相等,那么最长前后缀size就可以+1
    ne[i] = j;                   // 最后更新一下ne[i]
}

$每一次将字符串的s[i]和模式串的p[j + 1]进行匹配$

// KMP匹配过程:将s[i]与p[j + 1]进行匹配[当然这里为什么用j+1就说来话长了,毕竟当不匹配的时候是要对该下标前面的进行转移，所以与其用j-1，不如用j+1也就方便不越界了]
for (int i = 1, j = 0; i <= m; i++)
{
    while (j != 0 && s[i] != p[j + 1])  j = ne[j];   // 只要j没有退回起点,并且s[i]和p[j+1]不匹配,就可以通过next数组更新j
    if (s[i] == p[j + 1]) j++;                // 因为上面的循环结束有两种情况，1.j退回起点退无可退了，2.s[i]和p[j+1]终于匹配上了
    if (j == n)
    {
        cout <<  i - n << " ";                // 匹配成功,这里是根据题目要求的输出所有出现位置的起始下标（下标从0开始计数）
        j = ne[j];                           // 此时依旧使用next数组来更新使得省去已知匹配的前后缀
    }
}

$ \text{KMP} 算法可以视作状态机模型:基于字符串p的\text{KMP}自动机接受且仅接受以p为后缀的字符串，其接受状态为|p|。 $
$转移函数:$

$$ne(i, c) = \begin{cases} i + 1, & \text{if } p[i+1] = c \\ 0, & \text{if } p[1] \neq c \land i = 0 \\ ne(\pi(i), c), & \text{if } p[i+1] \neq c \land i > 0 \end{cases}$$

时间复杂度

$O(n+m)$

完整C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 1000010;

char p[N], s[M];             // pattern:模式串
int ne[N];                  // next数组

int main() 
{
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;

    // 求next数组过程:其实就是求最大前后缀长度，通过仿造下面KMP匹配的过程来求,可以将暴力求的o(n^2)复杂度降至o(n)
    for (int i = 2, j = 0; i <= n; i++)           // 注意这里i得从2开始,因为默认ne[1]=0,如果这里i从1开始,很明显会导致ne[1]=1,最终代码会出现TLE
    {
        while (j != 0 && p[i] != p[j + 1])  j = ne[j];   // 只要j没有退回起点,并且p[i]和p[j+1]不匹配,就可以通过next数组更新j
        if (p[i] == p[j + 1]) j++;   // 如果最终p[i]和p[j+1]相等,那么最长前后缀size就可以+1
        ne[i] = j;                   // 最后更新一下ne[i]
    }

    // KMP匹配过程:将s[i]与p[j + 1]进行匹配[当然这里为什么用j+1就说来话长了,毕竟当不匹配的时候是要对该下标前面的进行转移，所以与其用j-1，不如用j+1也就方便不越界了]
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j != 0 && s[i] != p[j + 1])  j = ne[j];   // 只要j没有退回起点,并且s[i]和p[j+1]不匹配,就可以通过next数组更新j
        if (s[i] == p[j + 1]) j++;                // 因为上面的循环结束有两种情况，1.j退回起点退无可退了，2.s[i]和p[j+1]终于匹配上了
        if (j == n)
        {
            cout <<  i - n << " ";                // 匹配成功,这里是根据题目要求的输出所有出现位置的起始下标（下标从0开始计数）
            j = ne[j];                           // 此时依旧使用next数组来更新使得省去已知匹配的前后缀
        }
    }
}