字符串匹配 – KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) ^[1] 。

——百度百科

KMP算法的核心是构建next数组，next数组也可以单独解决很多问题。

next数组维护的是 模式串前缀 与 模式串后缀 的匹配问题。

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <queue> 
#include <stack> 
#include <algorithm> 
#include <string> 
#include <map> 
#include <set> 
#include <vector> 
using namespace std; 

/**
 * @brief 构建 next Longest Prefix Suffix
 *        记录每个j前跳的位置 
 *        next[j]描述的是模式串的每一位作为最长后缀结尾时，对应的前缀结尾索引。
 * @param pattern 模式串
 * @param next 模式前跳位置记录
 */
void GetNext(const char *pattern, int *next) { 
    next[0] = -1; // pattern的第0位没有匹配的前缀串
    int j = -1; // j指向通过匹配的模式串结尾索引 -1代表没有前缀串
    for (int i = 1; pattern[i]; ++i) { 
      // 模式串的下一位(j + 1)和 i 不等 则j向前走 
      // j走到当前位置作为后缀 所对应的最长前缀结尾处
      //【此时可以保证i与j+1有公共小前缀】 再次判断(j + 1)和 i 是否相等
        while (j != -1 && pattern[j + 1] - pattern[i]) j = next[j]; 
        // 如果j+1 == i j向后走1位
        if (pattern[j + 1] == pattern[i]) j += 1; 
        // 记录next[i]位置的前跳位置
        next[i] = j; 
    }
    return;
}
/**
 * @brief KMP算法
 *        KMP可以用于流式匹配 因为不需要全部文本串 每次输入一个文本串字符 即可得出匹配结果（eg.敏感词过滤）
 * @param text 文本串
 * @param pattern 模式串
 * @return int 匹配索引
 */
int kmp(const char *text, const char *pattern) { 
    int n = strlen(pattern); 
    int *next = (int *)malloc(sizeof(int) * n); 
    GetNext(pattern, next); 
    // 文本串是一直向后遍历的
    for (int i = 0, j = -1; text[i]; i++) { // 自动机思想 输入一个i就可以得到一个j
        // j是模式串中 与文本串可以匹配上的部分的 末尾位置
        // j可以向前跳 && 文本串待匹配的位置i的值 != 模式串待匹配的位置j+1的值
        while (j != -1 && text[i] - pattern[j + 1]) j = next[j]; //j向前跳
        if (text[i] == pattern[j + 1]) j += 1; // 匹配上了 则j + 1
        if (pattern[j + 1] == 0) return i - j; // 模式串匹配到结尾了
    }
    return -1;
}

#define TEST(func, s1, s2) { \ printf("%s(\"%s\", \"%s\") = %d\n", #func, s1, s2, func(s1, s2)); \ }
    
int main() { 
    char s1[100], s2[100]; 
    while (cin >> s1 >> s2) { 
        TEST(kmp, s1, s2); 
    }
    return 0; 
}