题解：P3375 【模板】KMP （显眼包）

· · 题解

Update on 2025/7/28：将讨论区里提出的常见问题做出解答，应用新版格式，并删除开头废话。麻烦管理员通过。

如有问题欢迎在讨论区提出！

用途

在字符串初级算法里，而其中最经典的模型问题就是判断一个串是否是另一个串的子串。我们常用 KMP 算法解决这类问题。

题目描述

给定两个字符串 s_1 和 s_2，求出 s_2 在 s_1 中所有出现的位置和 s_2 的每个前缀 s' 的最长 border 的长度。

在本题解中，我用 n 代替 |s_1|（即 s_1 的长度），用 m 代替 |s_2|。

暴力匹配

枚举 s_1 的每一个起始位置 i(0\le i<n-m)，看从 i 位置开始往后长度为 m 的子串是否是可以和 s_2 匹配。

判断两个串匹配成功的条件是：两个串长度一致，两个串每一个对应位置字符都完全一样。

本做法时间复杂度为 O(nm)，只能得 70 分，比总司令高。

更优做法：KMP

定义

定义一个字符串性质——前缀后缀最大值，即题目中要求的 border（让你求那多半要用）。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。

我将字符串 s 的前缀 s' 的最长 border 的长度称为 next_{|s'|}，别问我为啥。

换句话说，next_i 就是遍历到字符串 s_2 的第 i 位时，与已经匹配成功的部分的后缀相同的最大的长度。我代码中的 kmp[i] 就是 next_i。

匹配过程

举例说明，其中 s_1 为 ABACABACABD，s_2 为 ABACABD。

先将 s_1 和 s_2 的第一位对齐并看对应位是否相同，我们发现一路畅通，但最后一个匹配失败了。若这时对齐 s_1 的第二位和 s_2 的第一位将 s_2 重新匹配一遍就成了暴力。

      i
ABACABACABD
ABACABD
      j

仔细回想 next 定义发现：失配后，我们可以直接跳到 next_j，即与已匹配部分相同的 s_2 最大前缀的最后一位的下一位，手动得出此时 next_j=2。然后就会变成这样：

      i
ABACABACABD
    ABACABD
      j

这样做，复杂度为 O(n+m)。

求 next

将 s_2 自己和自己匹配，过程和上面相仿。匹配到 j 失败时，记录 next_i 为 j。匹配时一个字符串不动，另一个向后移，i 为匹配到不动的 s_2 的位置，j 为匹配到要动的 s_2 的位置。

具体实现见代码。

实现

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int kmp[N],la,lb,j;
//kmp即Next数组,表示相同前缀后缀最大值(不是对称的最大值)
string a,b,A,B;

int main(){
    cin>>A>>B;
    a='\0'+A,b='\0'+B;
    la=a.size()-1,lb=b.size()-1;
    for(int i=2;i<=lb;i++){//求kmp
        while(j&&b[i]!=b[j+1]) j=kmp[j];
        if(b[j+1]==b[i]) j++;
        kmp[i]=j;
    }
    j=0;
    for(int i=1;i<=la;i++){//匹配
        while(j>0&&b[j+1]!=a[i]) j=kmp[j];
        if(b[j+1]==a[i]) j++;
        if(j==lb){printf("%d\n",i-lb+1);j=kmp[j];}
    }
    for(int i=1;i<=lb;i++) printf("%d ",kmp[i]);
    return 0;
}

::::

::::warning[讨论区常见问题]

问题

为什么求 kmp 数组（代码第 12 行）下标 i 要从 2 开始到 b.size()-1 结束啊？

回答

首先 i 以 b.size()-1 结束并不难理解，我加了个空字符 \0 来让字符串下标从 1 开始，但我用 b.size() 求出的大小会把 \0 算上，因此要减一。

然后回答为什么 i 要从 2 开始。先理解 kmp 数组的定义和作用，然后再手动推一下发现如果从 1 开始 kmp[1] 就会变为 1 而非 0 导致后面模式串与文本串比对时在 1 这个位置回跳时不断往下标为 1 的位置跳而死循环。

::::

点个赞再走呗。