之前模模糊糊的理解了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;
}