之所以说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算法其实也不是很难
