KMP

　　KMP算法 又称模式匹配算法，能够在线性时间内判定字符串 $B$ 是否为字符串 $A$ 的字串，并求出字符串 $B$ 在字符串 $A$ 中各次出现的位置

　　看到这个问题，通常会想到一个 $O(NM)$ 的朴素做法，这个我就不讲了

　　$Hash$ 也可以线性求解，这个处理字符串里所有前缀 $Hash$ 值就好了

　　还有其实我仿佛记得一个叫 $strstr$ 的函数跟这个有点关系，感兴趣的可以百度一下

　　下面进入正题

　　关于KMP算法的实现，主要分为两步：

　　1. 对字符串 $B$ 进行自我匹配，求出一个数组 $nxt$ ，其中 $nxt[i]$ 表示字符串 $B[1 sim i]$ 的前缀与后缀能够匹配的最大长度（当然这里的前缀和后缀都不能等于自身）

　　2. 然后就是借助 $nxt$ 数组高效地将字符串 $B$ 在字符串 $A$ 中进行匹配

　　$nxt$ 数组

　　1. 初始化 $nxt[1]=j=0$ ，假设 $nxt[1 sim i-1]$ 已求出，下面求解 $nxt[i]$

　　2. 尝试扩展匹配长度 $j$ ，如果扩展失败，令 $j$ 变为 $nxt[j]$ ，直至 $j$ 为 $0$ （这步比较玄学多举几个例子就意会了）

　　（补充：如果理解为将原串与匹配串上下比对，那么 $j=nxt[j]$ 就相当于将下面的匹配串向右移动一段距离，第二步中同理）

　　3. 如果能够扩展成功，匹配长度 $j$ 就增加 $1$ , $nxt[i]$ 的值就是 $j$

for(int i=2,j=0;i<=lb;i++){
    while(j&&b[j+1]!=b[i]) j=nxt[j];
    if(b[j+1]==b[i]) j++;
    nxt[i]=j;
}

View Code

　　$AB$ 串匹配

　　这步与第一步原理相同，第一步是将 $B$ 串与 $B$ 串匹配，这一步是将 $B$ 串与 $A$ 串匹配

for(int i=1,j=0;i<=la;i++){
    while(j&&b[j+1]!=a[i]) j=nxt[j];
    if(b[j+1]==a[i]) j++;
    if(j==lb){
        printf("%d
",i-lb+1);
        j=nxt[j];
    }
}

View Code

　　KMP算法实现过程就是这样

　　因为 $j$ 始终未负，所以 $j$ 减少的幅度总和不会超过增加的幅度总和，故 $j$ 的总变化次数至多为 $2(N+M)$ ，于是整个算法的时间复杂度为 $O(N+M)$

　　下面贴出完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define N 1000010

char a[N],b[N];
int la,lb,nxt[N]={0},flag=0; 

int main(){
    scanf("%s%s",a+1,b+1);
    la=strlen(a+1);
    lb=strlen(b+1);
    for(int i=2,j=0;i<=lb;i++){
        while(j&&b[j+1]!=b[i]) j=nxt[j];
        if(b[j+1]==b[i]) j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=la;i++){
        while(j&&b[j+1]!=a[i]) j=nxt[j];
        if(b[j+1]==a[i]) j++;
        if(j==lb){
            printf("%d
",i-lb+1);
            j=nxt[j];
            flag=1;//用于判定B是否为A的子串
        }
    }
    if(!flag) printf("-1
");
    
    return 0;
}

View Code