KMP算法的简单理解
总结一些在网上看到的关于KMP算法的简单理解，目前我的理解还很初步，很多东西还似懂非懂，目前先贴下来，期待以后慢慢懂。
KMP算法的基本原理
假设字符串S=BBC ABCDAB ABCDABCDABDE，搜索词P=ABCDABD。那么我们在执行搜索的时候进行下面的操作：
首先，字符串“BBC ABCDAB ABCDABCDABDE”的第一个字符与“ABCDABD”的第一个字符比较，因为不匹配，所以搜索词后移一位，直到移动到匹配的地方，即
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A |
然后我们就发现匹配了，于是开始使用搜索词P的第二个字符与字符串S下一个字符进行比较发现相匹配，然后继续比较……直到P的最后一个字符D与S中相应位置进行比较，发现S中为空格，即
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A | B | C | D | A | B | D |
如果是传统的方法，则是将字符串P的指针回到第一个字符，然后后移继续进行比较。这样的方法是暴力方法，复杂度太高。KMP算法是利用了已经知道的匹配信息，然后不再把“搜索位置”移回已经比较的位置再进行比较，而是继续往后移。这里利用的就是部分匹配值（Partial Match Value）。
| 部分匹配值的介绍
首先要了解“前缀”和“后缀”的概念。前缀是指除了最后一个字符以外，一个字符串的全部头部的集合，后缀是指除了第一个字符以外，一个字符串的全部尾部的集合。所谓部分匹配值就是前缀和后缀的最长的共有元素的长度。以ABCDABD为例，有以下情况：
所谓部分匹配，实质上指的是有时字符串头部和尾部会有重复。例如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。 |
我们进行“继续往后移”的移动位数的标准是用如下公式计算：
移动位数=已匹配的字符数-对应的部分匹配值
基于上面这个公式，我们可以看到，已匹配的字符数为6（ABCDAB），对应的部分匹配值为2，那么就将搜索词向后移动4位。如下所示：
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A | B | C | D | A | B | D |
依旧是如此，可以看到空格与C不匹配，搜索词还要继续往后移。此时已匹配的字符数为2（AB），对应的部分匹配值为0，所以往后移动2位。
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A | B | C | D | A | B | D |
此时空格与A不匹配，往后继续移动1位，得到如下所示。
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A | B | C | D | A | B | D |
这个时候发现D又不匹配，此时已匹配的字符数为6位，对应的部分匹配值为2，所以向右移动4位，得到如下所示。
| B | B | C | A | B | C | D | A | B | A | B | C | D | A | B | C | D | A | B | D | E | ||
| A | B | C | D | A | B | D |
此时，发现匹配，搜索完成。当然，如果想继续寻找后面是否还会有继续匹配的，可以继续移动7位（已匹配的字符数为7，对应的部分匹配值为0）。
我们换个角度来理解，假设P为主字串，而T为子串。当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。即
P[0 ~ k-1] == P[j-k ~ j-1]
因为:
当T[i] != P[j]时，有T[i-j ~ i-1] == P[0 ~ j-1]，由P[0 ~ k-1] == P[j-k ~ j-1]，必然：T[i-k ~ i-1] == P[0 ~ k-1]。
next数组的求解思路
讲完上面的原理，下面就是编程的实现，这里面最重要的就是根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。
实际上，next[j]的值（也就是k）表示，当P[j] != T[i]时，j指针的下一步移动位置。
我们在做题的时候来求next数组，可以通过手算，按照计算部分匹配值即可。要注意的是，next[1]=0，next[1]=1，next[n]是计算前面n-1个字符的部分匹配值，如果找到，那么next值是该长度加1，否则next值是1（其实就是0+1）。
但是，编写程序我们需要原理。如图2所示。此时j=0，如果这个时候不匹配，那么j已经在最左边，不可能移动了，所以这个时候应该是i来移动，所next[0]=-1。
图1
当j=1的时候，按照前面说的，我们应该将j移动到为T[0]的位置，所以实际上这里next[1]=0。
图2
对比图3中的两个图，我们发现当P[k] == P[j]时，有next[j+1] == next[j] + 1。其实这个是可以证明的：因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）这时候现有P[k] == P[j]，我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。（这里还需要多去理解理解）
图3
如果P[k] != P[j]，那么k=next[k]，如图4所示。
图4
nextval数组的求解思路
nextval[i]的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致，如果一致则用s[next[i]]的nextval的值作为nextval[i]，如果不一致，则用next[i]做为nextval[i]。
即以下格式：
nextval[i] = s[next[i]]==s[i]?nextval[s[next[i]]]:next[i]
KMP算法的代码
KMP算法：可以实现复杂度为O(m+n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<stdio.h> #include<string.h> void getNext(const char P[], int next[]) { int 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; } } int kmp(const char T[], const char P[], int next[]) { int n, m; int i, q; n = strlen(T); m = strlen(P); getNext(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) // 输出找到的位置 还可以判断i == n - 1 未找到 { printf("Pattern occurs with shift:%d\n", (i - m + 1)); } } } int main() { int i; int next[100] = { 0 }; char T[20], P[20]; scanf("%s%s", T, P); printf("%s\n", T); printf("%s\n", P); kmp(T, P, next); for (i = 0; i < strlen(P); ++i) { printf("%d ", next[i]); } printf("\n"); return 0; } |
