z3475 的博客

题解 P3375 【【模板】KMP字符串匹配】

KMP算法主要用于字符串匹配,但是其扩展能解决很多字符串问题。下面我来给大家讲解KMP算法 tips:以下数组均为从0开始

1、next数组

next数组的定义是对于一个字符串str,next[i]表示的是在str中

[0,next[i])以及 [i-next[i],i)

这两个区间中的字符严格相等的最大next[i]值(区间不能重叠

举个例子

a b c a b c b b a b c

0 0 0 1 2 3 0 0 1 2 3

[a] b c [a]=> next[4] = 1

[a] [b] c [a] [b] => next[5] = 2

[a] [b] [c] [a] [b] [c] => next[6]=3

画一张图意会

其中的线表示相同的一堆相同的字符,长方形指一个(一堆)字符,中间的省略号省略了一堆字符

手算不难得出,我们先不讲这个数组通过算法怎么生成的,我们先讲怎么用这个数组

2、KM

在介绍普通的KM算法前我们先回顾一下解决字符串查找的朴素算法

char s1[MAXN],s2[MAXN];//s1.find(s2);
int l1=strlen(s1),l2=strlen(s2);
int j=0,i=0;
while (i!=l1){
    if (s1[i]==s2[j]) i++,j++;//匹配
    else i-=j-1,j=0;//失配
    if (j==l2){
        cout << i-j+1 << endl;
        j=0;//相当于失配
    }
}

明显失配时的移动可以优化,那怎么优化呢,我们就要用到next[]

根据next[]我们可以画一张关于失配图

最佳的移动是这样

所以检测到失配时

i可以保留,j = next[j-1]

但是j肯定有等于0的情况,j - 1 不就越界了吗?

-我们就在计算时加一个F()函数检测j - 1是不是越界了

于是用next[]优化后的代码就出来了

#define F(x,nxt) (x<0?-1:nxt[x])
int i=0,j=0;
while (i!=l1){
    if (j==-1||s1[i]==s2[j]) i++,j++;
    else j=F(j-1,nxt);
    if (j==l2){
        cout << i-j+1 << endl;
        j=F(j-1,nxt);
    }
}

next[]的计算

考虑以下字符串,我们要算出它的next[]

a b c a b c a b

手算得

0 0 0 1 2 3 1 2

显然对于每一个next[i]一种情况可以这么弄

next[i] = next[i-1] + 1 if str[i]==str[next[i-1]]

那当str[i]!=str[next[i-1]]的情况呢

先给一个结论,然后我们来试着证明它

我们就令j = next[i-1]

while (1){

    if (str[i]==str[j]) {next[i] = j + 1;break;} //①
    if (str[i]!=str[j]) j = next[j] - 1;  //②

}

next[i] = j + 1,str[i]==str[j]

j = next[j] - 1,str[i]!=str[j]

一旦执行到①,next[i]就算完了 证明过程我们用一张图来意会

我们要求箭头指向的那个字符的next值,这里我们假设前面字符的next值已经求完了

但是我们可能会检测到②这种情况,图就变成了这样

这样的话显然是正确的,剩下的证明过程,提一个主要思路

1、证明真正的next值<算出来的值是假的

2、证明真正的next值>算出来的值是假的

又在上一章讲到我们还要把next[]往后移一位且next[0]=-1

怼在一起有代码

#include<bits/stdc++.h>
#define F(x,nxt) (x<0?-1:nxt[x])
using namespace std;
char s2[1000010],s1[1000010];
int nxt[1000010];
int main(){
    scanf("%s%s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    //计算nxt[]
    nxt[0]=0;
    for (int i=1;i<l2;i++){
        int j=nxt[i-1];
        while (j&&s2[i]!=s2[j]) j=nxt[j-1];
        if (s2[j]==s2[i]) nxt[i]=j+1;
        else nxt[i]=0;
    }
    //匹配 
    int i=0,j=0;
    while (i!=l1){
        if (j==-1||s1[i]==s2[j]) i++,j++;
        else j=F(j-1,nxt);
        if (j==l2){
            cout << i-j+1 << endl;
            j=F(j-1,nxt);
        }
    }
    for(int i=0;i<l2;i++) cout << nxt[i] << ' ';
    return 0;
}

2018-08-19 23:25:44 in 题解