朴素模式匹配算法的存在大量的重复匹配操作，时间复杂度为O(m*n)，其中m表示主串的长度，n表示模式串的长度，但是算法好理解。另外有一种高效的算法，被称为KMP，该算法的目标就是去掉多余的重复匹配过程，但是算法很难理解，主要是通过构造一个next[]数组来实现，可以实现线性的时间复杂度O(m+n)，可以参考网络是一篇比较优秀的博文：
1 /* KMP模式匹配算法 2 */ 3 void get_next(const char T[], int next[]) 4 { 5 int j = 0, k = -1; 6 7 next[0] = -1; 8 while (T[j] != ' '){ 9 if (k == -1 || T[j] == T[k]){ 10 ++j; ++k; 11 if (T[j] != T[k]){ 12 next[j] = k; 13 }else{ 14 next[j] = next[k]; 15 } 16 }else{ 17 k = next[k]; 18 } 19 } 20 } 21 22 int IndexKMP(const char S[], const char T[], int pos) 23 { 24 int index = 0, i = pos, j = 0, len = strlen(T); 25 int *next = (int*)malloc(len * sizeof(int));//定义一个next[]数组 26 27 get_next(T, next);//分析T串,得到next[] 28 while (S[i] != ' ' && T[j] != ' '){ 29 if (S[i] == T[j]){ 30 ++i; ++j;//两字符相等则继续 31 }else{ 32 index += j - next[j]; 33 //j退回合适位置,i值不变 34 if (next[j] != -1){ 35 j = next[j]; 36 }else{ 37 j = 0; 38 ++i; 39 } 40 } 41 } 42 //free(next); 43 if (T[j] == ' '){ 44 return index;//匹配成功,返回主串中起始下标 45 }else { 46 return -1; 47 } 48 }
为了加深对该算法的理解，再列出几篇参考文章：