也许现在用过电脑的人都知道大多数带文本编辑功能的软件都有快捷键ctrl f。 (这个功能主要完成“查找”、“替换”和“全部替换”的功能，其实这是典型的模式匹配应用，在文本文件中搜索字符串。
1 .模式匹配的模式匹配模型大概是这样的。 给出两个字符串变量s和p，其中s是目标字符串，其中包含n个字符。 p称为模式列，包含m个字符，其中m=n。 从s的指定位置，通常是s的第一个位置开始检索模式p。 如果找到，则返回模式p在目标字符串中的位置，即p的第一个字符在s中的下标。 如果在目标列s中找不到模式列p，则返回-1。 这就是模式匹配的定义。 看看如何实现模式匹配算法。
2 .朴素的模式匹配朴素的模式匹配算法非常简单易懂。 可能的想法是，从s的第一个字符S0开始，将p中的字符依次与s中的字符进行比较，如果S0=P0 …… Sm-1=Pm-1，则证明匹配成功，不进行剩下的匹配就返回下标0。 如果有一步Si！=Pi也不需要比较p中剩下的字符，匹配并不成功。 然后，从s中的第二个字符与p中的第一个字符进行比较。 同样，你知道Sm=Pm-1，或者找到某个I制作Si。=到s-1为止。 类推只要知道s中第n-m个开始字符，且匹配尚未成功，就证明s中不存在模式p。 (请想想为什么这里强调是n-m。 )此代码的实现非常简单，具体而言，应该开始参考strstr函数的内部实现。 你可以浏览百度百科，链接http://baike.Baidu.com/view/745156.htm，但这里不写。 另外，必须赶紧进入正题的KMP。
3 .快速模式匹配算法(KMP )朴素模式匹配效率不高的主要原因是进行了重复的字符比较。 下一次比较与上次比较没有任何联系，是朴素模式匹配的缺点，但实际上上次比较的比较结果是可用的，这就产生了快速模式匹配。 在朴素的模式匹配中，目标列s的下标的移动是一步一步的，但这实际上并不好。 移动步数不需要为1。
请假设现在的匹配情况如下。 S0 …… St St 1 …… St j和P0 P1…… Pj，现在要匹配的字符是St j 1和Pj 1，还有St j 1。=Pj 1，言外之意是St St 1……St j和P0 P1……Pj完全一致。 那么，此时，s的下一个匹配开始位置是什么？ 在朴素的模式匹配中，下次比较应该从St 1开始，并且应该比较St 1和P0，但在快速模式匹配中不是。 通过快速模式匹配选择St j 1和Pk 1进行比较，k是什么呢？ k是P0 P1……Pk和Pj-k Pj-k 1……Pj完全一致的值，可以为k=next[j]。 因此，P0 P1……Pk和St j-k St j-k 1 ……St j完全一致。 下一个匹配的两个字符必须是St j 1和Pk 1。 s和p都没有追溯到下标0，这是KMP快的理由。
这里发生了关键问题。 这个k怎么能弄到？ 如果这个k的值复杂度高，这个想法就不好了。 实际上，这个k只与模式列p有关，而且要求m个k，k=next[j]，所以计算一次并存储在next数组中就可以了。 而且，时间的复杂度与m有关(线性关系)。 具体来看如何求出next数组的值，即求出k。
用归纳法求出next[] :设定next[0]=-1，如果知道next[j]=k，则求出next[j 1]。
(1)如果Pk 1=Pj 1，显然如果next[j1]=k1.PK1的话！=Pj 1，next[j 1] next[j]，然后找h k取p0p 1……ph=pj-hpj-h1……pj=PK-hpk-h1……PK。 即h=next(k )； 明白了吧。 这是一个迭代的过程。 (也就是说，以前的结果有助于求出今后的值)
)2)在不存在这样的h的情况下，P0 P1……Pj 1中没有前后相等的子串，因此next[j 1]=-1。
)3)存在这种h时，继续检查Ph和Pj是否相等。 在其中找到相等的情况，或者确定为-1并求出next[j 1]的过程结束。
看看实现的代码：
视图代码
int next[20]={0}；
注意//返回值是数组next，如果next[j]=k，则为保存k个值的位置
//的话str [0] str [1]…str [ k ]=str [ j-k ] str [ j-k1 ]…str [ j ]
//这样，如果des[t j 1]和pat[j 1]匹配失败，则下一个匹配位置为des[t j 1]和next [ j1]
voidnext(charstr[]，int len ) )。
{
next[0]=-1；
for(intj=1； j len； j )
{
int i=next[j-1]；
while(str[j]！=str[I1]I=0(//迭代的过程
{
i=next[i]；
}
if(str[j]=
= str[i+1]){
next[j] = i+1;
}
else
{
next[j] = -1;
}
}
}
现在有了next数组保存的k值，就可以实现KMP算法了：
View Code
//des是目标串，pat是模式串，len1和len2是串的长度
int kmp(char des[],int len1,char pat[],int len2)
{
Next(str2,len2);
int p=0,s=0;
while(p < len2 && s < len1)
{
if(pat[p] == des[s])
{
p++;s++;
}
else
{
if(p==0)
{
s++;//若第一个字符就匹配失败，则从des的下一个字符开始
}
else
{
p = next[p-1]+1;//用失败函数确定pat应回溯到的字符
}
}
}
if(p < len2)//整个过程匹配失败
{
return -1;
}
return s-len2;
}
时间复杂度：对于Next函数近似接近O(m)，KMP算法的时间复杂度为O(n)，所以整个算法的时间复杂度为O(n+m)
空间复杂度：
多引入了O(m)的空间复杂度。
4.应用KMP的一道面试题给定两个字符串是s1和s2，要判定s2是否能够被s1做循环移位得到的字符串包含。例如s1=AABCD，s2 =CDAA，返回true，因为s1循环移位可以变成CDAAB。给定s1=ACBD和s2=ACBD则返回false。
分析：不难发现对s2移位得到的字符串都将是字符串s1s1的子串，如果s2可以有s1循环移位得到，那么s2一定是s1s1的子串，这时KMP算法是不是就很管用了呢。