【算法】KMP算法

背景

由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称$KMP$算法)。

介绍

$KMP$算法,又称模式匹配算法,能够在线性时间$O(N+M)$判定字符串$A[1$~$N]$是否为字符串$B[1$~$M]$的子串,并求出$A$在$B$中出现的次数。

详细解释

$KMP$算法分为两步:
1.对字符串$A$进行自我匹配,求出一个数组$next$,其中$next[i]$表示$A$中以$i$结尾的非前缀子串于$A$的前缀能够匹配的最大长度。
$next[i]=max(j),j < i\ and\ A[i-j+1$~$i]=A[1$~$j]$
2.对$A$和$B$进行匹配,求出一个数组$fail$,其中$fail[i]$表示$B$中以$i$结尾的字串于$A$的前缀能够匹配的最大长度。
$fail[i]=max(j),j<i\ and\ B[i-j+1$~$i]=A[1$~$j]$

代码

next[1] = 0;
for(int i = 2,j = 0;i <= n;i++){
    while(j > 0 && a[i] != a[j + 1]){
        j = next[j];
    }
    if(a[i] == a[j + 1]){
        j++;
    }
    next[i] = j;
}

for(int i = 1,j = 0;i <= m;i++){
    while(j > 0 && (j == n || b[i] != a[j + 1])){
        j = next[j];
    }
    if(b[i] == a[j + 1]){
        j++;
    }
    f[i] = j;
    if(f[i] == n){}//This is the each appear
}