之所以说KMP磨人是因为,他真的不怎么好懂,就算懂了,也不怎么好写0.0也有可能是我太菜了
KMP算法就是为了应对暴力匹配字符串带来的庞大的消耗,总的来说就是在匹配字符串的过程中如果发生匹配失败,不采用暴力匹配的方法直接从当前字符串的下一个位置开始匹配,而是最大程度的把匹配串向右移动尽可能多的字符。当然这里的移动并不是随便移动,而是根据一个移动表格(next数组)来进行移动
暴力匹配的思想就是逐个匹配,但是这是KMP怎么会这么low,当然对于下面这个字符串,刚开始可能和暴力匹配差不多
BBC ABCDAB ABCDABCDABDE
ABCDABD
依旧不相等,继续整体后移
BBC ABCDAB ABCDABCDABDE
#ABCDABD
整体移动到下面位置时,匹配成功一个字符
BBC ABCDAB ABCDABCDABDE
### ABCDABD
然后匹配一次对后面的字符进行匹配
BBC ABCDAB ABCDABCDABDE
### ABCDABD
到这个位置匹配失败,按照暴力匹配的方法应该将匹配串的头和目标串的第6个字符进行比较,但是根据KMP的思想,应该在出现错误的基础上,最大限度的右移匹配串
BBC ABCDAB ABCDABCDABDE
### ABCDABD
然后根据之前构造好的Next表(后续会说明Next表的原理),在D位置匹配失败,然后匹配成功的最后一个字符是B,B对应的Next数组值为2,这个时候我们就应该将字符串后移:(已经匹配的字符个数-部分匹配值)个字符
ABCDABD
000012
因为已经匹配的字符数是6,部分匹配值是2,所以得出字符串向后移动4个单位
BBC ABCDAB ABCDABCDABDE
### ####ABCDABD
然后按照常规的匹配的规则继续匹配,直到出现下图的情况。再按照KMP的处理方法,尽可能的后移匹配串,知道匹配成
BBC ABCDAB ABCDABCDABDE
### ####ABCDABD
到这里都好懂,然后就开始想这个Next数组是怎么求出来的?然后我就懵逼在Next数组上
说到这了都,问题就演变成了如何求Next数组的部分匹配值了。网上其他的博客上还引入了前缀和后缀的概念,但是我认为没有什么必要。所谓的部分匹配值就是,从头开始对匹配串进行重复查找,简单的来说A B C D A B D,1-4的部分匹配值为0,但是5-6出现了重复组A B,第7位虽然也在前面出现,但是组A B D没有在前面出现,所以D位置的部分匹配值为0
OK,原理大概就是这样,剩下的一个问题就是代码了
其实整体很难解决的就是一个Next数组的构造和KMP的主程序
根据上面的原理实际上Next数组就很好实现了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void setNext(const char P[],int next[]) { int q,k;//q:模版字符串下标;k:最大前后缀长度 int m = strlen(P); next[0] = 0; for (q = 1,k = 0; q < m; ++q) { while(k > 0 && P[q] != P[k]) k = next[k-1]; if (P[q] == P[k]) { k++; } next[q] = k; } } |
既然有了Next数组,那就可以很愉快的写KMP函数了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
int kmp(const char T[],const char P[],int next[]) { int n,m; int i,q; n = strlen(T); m = strlen(P); setNext(P,next); for (i = 0,q = 0; i < n; ++i) { while(q > 0 && P[q] != T[i]) q = next[q-1]; if (P[q] == T[i]) { q++; } if (q == m) { printf("匹配串开始的位置是:%d\n",(i-m+1)); } } } |
这么看的话磨人的KMP算法其实也不是很难