【ACWing 算法基础】KMP

一. 模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

二. 总结

• 将暴力的 O(N*N) 降为了O（N）
• 解题方法：

1. 先写匹配的部分，再写 next 数组的部分，思路一样的
2. next，for 内部（i = 1， j = 0） ：
   1. 匹配不成功则一直回退，直到 j = 0 时没有办法
   2. 回退之后，匹配成功，j++ 模式串向前推进
   3. 判断 j == m，看是否比较完
3. next，for 内部（i = 2， j = 0） ：将 s 换为 p
   1. 匹配不成功则一直回退，直到 j = 0 时没有办法
   2. 回退之后，匹配成功，j++ 模式串向前推进
   3. ne[i] = j，更新 next 数组

• 详细解析
• 图解：
  • 匹配字符串
    
  • 求 next 数组
    

三. 例题

• 831. KMP字符串

AC代码:

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char s[M], p[N];
int ne[N];  // 不取next，防止与std::next冲突

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;  // +1是因为主串i从1开始取，方便理解
    
    // 求next[]数组
    for (int i = 2, j = 0; i <= n; ++i) {  // i从2开始是因为ne[1]代表模式串第1个匹配失败，j就得从0重新开始
        while (j && p[i] != p[j + 1])   j = ne[j];  // 匹配失败，回退
        if (p[i] == p[j + 1])   ++j;  // 回退之后匹配主串当前字符，继续推进主串，成功则推进模式串
        ne[i] = j; // 更新next数组
    }
    
    // 匹配操作
    for (int i = 1, j = 0; i <= m; ++i) {  // 这里j代表当前匹配失败的前一位，
                                          // i从1开始是因为与j+1对应比较好理解，此时不匹配时，ne的下标为j
        while (j && s[i] != p[j + 1])   j = ne[j];  // 匹配失败，回退
        if (s[i] == p[j + 1])   ++j;  // 回退之后匹配主串当前字符，继续推进主串，成功则推进模式串
        if(j == n) {  // 模式串全部匹配成功
            cout << i - n << ' ';
            j = ne[j];  // 重新开始匹配
        }
    }
    
    return 0;
}