假设有两个字符串string（s代替）和pattern（p代替），其中pattern是要在string中查找的模式。即确定pattern是否在string中并返回其坐标数值。这一过程就称模式匹配。
c语言中最基本的就是..strstr函数，但是其效率不高，自己定义的算法完全可以做得更好。
介绍KMP算法之前，先介绍一下最简单的暴力枚举的算法（KMP是在这个算法的基础上改进而来的）
1.BF_Match(BF:brute froce，暴力枚举）
举例说明：
S: ababcababa
P: ababa
BF算法匹配的步骤如下
（补充一下，当i回溯的时候，即“失配”(s[i] != p[j])时） 以上过程图摘自：
下面给出实现代码：
<span>/*——————暴力匹配—————— 注意const的用法，去掉之后编译会出现waring，看看 */ #include <stdio.h> #include <string.h> int BFmatch(const char *s, const char *t) { int i = 0; while(i < strlen(s)) { int j = 0; while(s[i] == t[j] && j < strlen(t)) { i++; j++; } if(j == strlen(t)) return i - strlen(t); i = i - j + 1;//为什么是i - j + 1画一下图就明白了.. } return 0; } int main() { const char * s = "ababcababa"; const char * t = "ababa"; int pos = BFmatch(s,t); printf("The position is : %d\n",pos); return 0; } </span>算法分析：我们可以看出，i并不是线性的推进（经常回溯...）所以这个肯定效率不高，当p不是s的模式匹配的话，时间复杂度是O(m * n) m是s长度，n是p的长度。
理想的时间复杂度是O(strlen(string) + strlen(pattern))，于是三个大牛就想出来了一个算法。
2.KMP算法
D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）
下面是KMP算法的流程，非常重要！！
假定:
pattren = “a b c a b c a c a b"
字符串s:
s = s[0]s[1]s[2].........s[m-1]
假设要判断是否存在从s[i]开始的匹配。
1.如果s[i] != a(p[0]),那么显然下次从s[i+1]与a比较。
2.如果s[i] = a 但是 s[i+1] != b(p[1])，那么显然进行s[i+1]与a的比较。
3.如果s[i]s[i+1] = "ab"，但是s[i+2] != c，即下述情况。
(以上的分析作为基础，需要好好理解一下，不成问题）
s = ".....a b ? ? ? ? ......"
其中s的第一个?代表 s[i+2] != c，因此，搜索的下一步应该是对s[i+2]和a(p[0])比较！
（这是显而易见的，BF做法的话i就要回溯到i+1了，但其实没有必要回溯，因为s[i]s[i+1] = "ab"是既定事实，即s[i+1]是b(p[1])了，绝对不可能是a了)————这句话是KMP的一个重点。
依次类推，当出现下述情况时：
s = "....a b c a? ? . . . ?"
p = " ab c a b c a c a b"
假定出现了pattern前四个字母的匹配，然后失配，即s[i+4] != b
通过观察可以得出，匹配搜索可以继续把s[i+4]与p的第二个字符b(红色标记)进行比较。而不必进在s中对i进行回溯，这就是我们想要的线性算法。
（以上的分析是线性算法的由来，理解KMP算法的第一步）
如果上述的文字搞得大家云里雾里，不妨看下面这张图：
在阐述了原理之后，我们剩下一个最主要的问题：
出现失配的情况下，应当将p字符串向右滑动多少？？
实现这个过程，就是KMP算法的核心。
为了解决这个问题，引入了一个函数————模式失配函数。（引自《数据结构》（c语言版））
(PS:如果不明白这个函数的意义，请看此链接：?id=3731）
*模式失配函数：
定义模式失配函数为：next[]。