KMP算法是一种高效的前缀匹配算法，在传统蛮力（BF）匹配算法的基础上改进的地方在于每次移动的距离不是1可以是更大，没有进行回溯，BF算法的时间复杂度是O(m*n)，而KMP算法的时间复杂度是O(m+n)。
假设执行第i+1趟匹配时，如果比较模式串P中的第j个字符时不匹配，也就是有：
T[i,i+1,...,i+j-1]=P[0,1,...,j-1]，T[i+j]≠P[j] (1)
BF算法下一趟是从目标的第i+1位置开始与模式串比较。
如果匹配成功则有
T[i+1,i+2,...,i+m]=P[0,1,...m-1] (2)
如果模式串P有如下特征
P[0,1,...j-2]=P[1,2,...j-1] (3)
由（1）可知
T[i+1,i+2,...,i+j+1]=P[1,2,...j-1] (4)
由（3）（4）可知
T[i+1,i+2,...,i+j+1]≠P[0,1,...j-2] (5)
故由
T[i+1,i+2,....,i+m]≠P[0,1,...m-1]
所以第i+2趟是匹配可以不需要进行，因为一定不能匹配。
类似可以推得
P[0,1,...k-1]=P[j-k-1,j-k,...j-1]
这时才有
P[0,1,...k-1]=P[j-k-1,j-k,...j-1]=T[i+j-k,i+j-k+1,i+j-1]
模式串P从当前位置直接向右移动 j-k 位置，使模式串P的第 k 个字符P[k]与目标串T中的第i+j个字符对齐开始比较（前面 k 个已经匹配）。
造成BF算法效率低的主要原因是在算法执行过程中有回溯，而这些回溯是可以避免的。KMP算法的关键是在匹配失败时，确定下一次匹配的位置，设next[j]=k，表示当模式串P中第j个字符与母串T相应字符不匹配时，模式串P中应当由第K个字符与目标串中刚不匹配的字符对齐继续进行比较。
例如，模式串P="abaabcac"，其对应的next[j]如下：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| t[i] | a | b | d | a | b | c | d | e |
| next[i] | -1 | 0 | 0 | 0 | 1 | 2 | 0 | 0 |
next数组构造：
╔ -1， j=0;
next[j]= ║max{k| 0<k<j 且 P[0,1,...,k-1]=P[j-k,j-k+1,..j-1}
╚ 0， 其他情况
next数组求解是一个递推过程，
设next[j]=k，则有
P[0,1,...k-1]=P[j-k,j-k+1,...,j-1]
next[j]= ╔ max{k| 0<k<j 且 P[0,1,...,k]=P[j-k,j-k+1,..j-1}
╚ 0， 其他情况
如果P[k]=P[j]，有 next[j+1]=next[j]+1=k+1。
如果P[k]≠P[j]，有 P[0,1,...,k]≠P[j-k,j-k+1,...j],
假设next[j+1]=h+1，则有下式成立
P[0,1,...h]=P[j-h+1,j-k+1,...j] P[h]=P[j]
又因为
P[0,1,...h-1]=P[j-h,j-k+1,...j-1]=P[k-h,k-h+1,k-1] （next[k]=h的情况）
即此时实际只需要满足 next[k]=h（前面已经求解过）时，P[h]=P[j] 就有next[j+1]=h+1，否则（不存在这样的h）next[j+1]等于0。
由此可以得到计算next的递推公式
#include#include int next[32] = {-999};/* 返回模式串T在母串S中第pos个字符的位置 */int index_BF(char *S, char *T, int pos){ int i; int j; i = pos; j = 0; while ( (i < strlen(S)) && (j < strlen(T)) ) { if (S[i] == T[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } /* 注意strlen(T)意味着j的取值范围为0 ~ (strlen(T) - 1) */ if (strlen(T) == j) { return i - strlen(T); } else { return -1; }}/* 计算模式串T的next数组 */void get_next(char *T, int *next){ int k = -1; int j = 0; next[j] = k; // 这里的主串和模式串都是同一个字符串 while (j < strlen(T)) { // 如果模式串游标已经回退到第一个字符 或者 匹配成功 if ( (k == -1) || (T[j] == T[k]) ) { ++k; // 注意是先加后使用 ++j; next[j] = k; } else // 匹配不成功，k就回退到上一个next值 { k = next[k]; } }}int index_KMP(char *S, char *T, int pos){ int i; int j; i = pos; j = 0; while ( (i < strlen(S)) && (j < strlen(T)) ) { /* j = -1 表示next[0], 说明失配处在模式串T的第0个字符。所以这里特殊处理，然后令i+1和j+1。*/ if ( (j == -1) || S[i] == T[j]) { i++; j++; } else { j = next[j]; } } if (strlen(T) == j) { return i - strlen(T); } else { return -1; }}int main(void){ char *s = "ababcabcacbab"; char *t = "abcac"; int pos = 0; int index; printf("================ BM ==============\n"); index = index_BF(s, t, pos); printf("index = %d\n", index); printf("================ KMP ==============\n"); get_next(t, next); index = index_KMP(s, t, pos); printf("index = %d\n", index);}