KMP 算法详解

时间:2021-01-31 16:37:39

之前模模糊糊的理解了KMP,结果由于并不是完全弄清楚而导致自己在一道题目上疯狂的T,似乎是next函数写的有问题,于是痛心疾首的回来写一篇报告,警示自己

对KMP来说,匹配串的next数组是重中之重,通过next的跳跃,大大提高了匹配的速度

那么首先next 是什么呢?一句话的事情

这次没配上,下一次找谁配

换句话说,就是

当next[i] 大于 0 时,第 i 位的数字不一定与字符串的开头的相应位置匹配上

举个栗子

首先next[0] = -1 //第一个点都匹配不上当然就回家吃饭了啊

0

1

2

3

4

5

6

7

8

9

a

b

a

b

a

b

c

c

c

c

-1

0

0

1

2

3

4

0

0

0

next[1] = 0;

next[2] = 0;

很好理解,他们如果没有被匹配到,当然要去找第一个字符啊,第一个字符也匹配不了,当然就回家种地了

next[3] = 1

next[4] = 2

next[5] = 3

next[6] = 4

然而到第三位的时候,却不为0,不难看出,a[2] == a[0],这时候如果a[3]没有被匹配到,就可以访问a[1]看是否能匹配,4.5同理。

例如:

A     b     a     b     a     b     a     b     c      c      c      c

A     b     a     b     a     b     c      c      c      c

当匹配到如下字符时,发现不同,则回到↑所指位置再开始匹配,

换句话说,next[i] 就是在 i 前,产生了一个 next[i] 个字符的循环(前next[i]-1个字符与首next[i]-1个字符相匹配)

当解决next后,KMP就很简单了

i = 0 , j = 0

匹配串与被匹配串进行匹配,字符相同时

i++, j++;

当字符串不同时

i 不变(因为没有匹配上),j回到next[j](匹配串中的循环部分)

当 j = -1 时

i++,j=0 (从下一个字符开始,重新匹配)

KMP 不用像BF算法那样回溯,因为next数组处理了循环部分

不好理解的话,手动模拟一下样例

a a a b a a a b a a a a

a a a a

手模总是有助于理解的

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int Next[100];
void get_next(char *a)
{
int k = -1;
int j = 0;
Next[j] = k;
while(a[j] != '\0') {
if(k == -1 || a[j] == a[k]) {
k++;j++;
Next[j] = k;
}else k = Next[k];
}
}
int KMP(char S[],char T[])
{ get_next(T); int i=0;
int j=0;
while(S[i]!='\0' && T[j]!='\0'){
if(j == -1 || S[i] == T[j]){
i++;
j++;
}
else j = Next[j];
}
if(T[j]!='\0') return -1;
else return i-j+1;
} int main()
{
char a[100],b[100];
cin>>a>>b;
get_next(b); cout<<KMP(a,b)<<endl;
}