【笔记】Knuth-Morris-Pratt 算法

Part 1 简介

模式串匹配，就是给定一个需要处理的文本串（理论上应该很长）和一个需要在文本串中搜索的模式串（理论上长度应该远小于文本串），查询在该文本串中，给出的模式串的出现有无、次数、位置等。

Part 2 前缀函数

给定一个长度为 $n$ 的字符串 ，其前缀函数被定义为一个长度为 $n$ 的数组$Next$。其中 $n$ 为既是子串 $s[0…i]$ 的前缀同时也是该子串的后缀的最长真前缀（proper prefix）长度。一个字符串的真前缀是其前缀但不等于该字符串自身。根据定义， $Next[0] = 0$ 。
$$
Next[i] = \max_{k = 0 \dots i}{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]}
$$

Part 3 KMP代码实现

/*
 * @Author: thyzzs
 * @Date: 2019-11-13 15:27:35
 * @LastEditTime: 2019-11-13 16:48:08
 */
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX_N 1000005
using namespace std;

char str[MAX_N], pattern[MAX_N];
int Next[MAX_N];
int cnt;

inline void get_Next(char *p, int p_len) {  //预处理Next数组
    Next[0] = 0, Next[1] = 0;
    for (register int i = 1; i < p_len; i++) {
        int j = Next[i];
        while (j && p[i] != p[j]) {
            j = Next[j];
        }
        Next[i + 1] = (p[i] == p[j]) ? (j + 1) : 0;
    }
    return;
}

inline int kmp(char *s, char *pat) {  // s中匹配pat
    int cnt = 0;
    int last = -1;
    int s_len = strlen(s), p_len = strlen(pat);
    get_Next(pat, p_len);
    int j = 0;
    for (register int i = 0; i < s_len; i++) {  //匹配s和pat的每个字符
        while (j && s[i] != pat[j]) {
            j = Next[j];  //失配，根据Next[]找到j的回溯位置
        }
        if (s[i] == pat[j]) j++;  //当前位置字符匹配，继续进行
        if (j == p_len) {
            printf("%d\n", i + 1 - p_len + 1);  //因下标从1开始，所以+1
                                                //输出匹配的位置
            /*
            if (i - last >= p_len) {  //判断新的匹配和上一个匹配能否分开
                cnt++;
                last = i;  //last指向上一个匹配的末尾位置
            }  //输出匹配个数cnt
            */
        }
    }
    for (register int i = 1; i <= p_len; i++) {  //因下标从1开始，所以i加了1
        printf("%d ", Next[i]);
    }
    return cnt;
}

int main() {
    scanf("%s", str);
    scanf("%s", pattern);
    kmp(str, pattern);
    // printf("%d\n", kmp(str, pattern));
    return 0;
}