KMP算法可以在O(n+m)的时间数量上完成串的模式匹配操作。
n指的是主字符串的长度，m指的是模式字符串的长度。
求next数组的算法：
void get_next(char T[], int next[]) { i = 1; next[1] = 0; j = 0; while( i <= T[0]) { if(j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } }
KMP匹配算法：
int KMP(char S[], char T[], int next[], int pos) { i = pos; j = 1; while(i <= S[0] && j <= T[0]) { if(j == 0 || S[i] == T[j]) { ++i; ++j‘ } else j = next[j]; } }
KMP算法的主要优点是主串不回溯，且在主串与子串有很多“部分匹配”时才显得快。
原文：http://www.cnblogs.com/profinder/p/5874928.html