字符串模式匹配是指找到特定模式字符串在长字符串中出现的位置。
朴素的模式匹配算法
可以直观地编写以下代码，找出模式列在长字符串中出现的位置。
/*朴素的模式匹配算法
功能：字符串的模式匹配
参数：
s :目标字符串
p :图案列
pos :开发匹配的位置
返回值：
一致了。 返回模式列位于目标列的实际位置
火柴失败了。 -1*/
intmatch(constchar*s，const char * p，intpos ) intpos； int j=0； while(s[I]！=' ' p[j]！=' ' ) {if(s[I]==p[j]}{
I；
j；
}else{
i=i - j 1；
j=0；
}
}if(p[j]==' ' ) return i -j； else
返回- 1；
}
在上面的代码中，s是目标列，p是模式列，pos指定从s的哪个位置匹配p。 其实现思想也很简单：
如果s[i]==p[j]，则目标字符串和模式字符串指针都向后移动1位，进行匹配。 还有s[i]！=p[j]时，即匹配失败时，同时追溯目标字符串和模式字符串的指针，j=0时目标字符串的指针I追溯到下一个位置。
的模式匹配算法的复杂度为： o((n-m1 ) m ) n为目标列的长度，m为模式列的长度。
从其实现思想不难看出，该算法效率低下的原因是匹配不成功时主列和模式列指针的回溯。
是否有算法在模式列与主列匹配不成功时，不使用指针回溯而进行下一个回合的匹配？
了解KMP算法
朴素字符串模式匹配算法在主字符串与模式字符串字符不匹配的情况下，无论已经匹配的字符数如何，都追溯指针，开始下一次匹配。
这是非常低效的。 KMP算法基于朴素模式匹配算法，在匹配不成功时，不回溯主串指针而实现模式匹配的时间复杂度
降至(o )纳米)。
对KMP算法的理解，在网上查找了很多资料，也看到了算法导论的记述，一直一知半解。 忙得不可开交，为了使图案列、主列看起来都是直线，试着进行了以下导出，才恍然大悟。
KMP算法的核心思想是，在s[i]和p[j]不匹配的情况下，不将指针追溯到主串，而是在模式串中的p处查找k，在s[i]和p[k]处进行下一轮匹配
在此，由于主串s和模式串p都被视为一条直线，因此如果S[i]和P[j]匹配不匹配，则：
图1 s[i]和p[j]的匹配不顺利
即，p[1…j-1]==s[i-j 1，…，i-1]。
p[j]和s[i]不一致。 要在图案列p[1，…，j-1]中确定位置k(1=k j-1，并在p[k]和s[i]中进行以下匹配，k必须满足以下条件：
p[1，k-1]==s[i-k 1，i-1]。
以直线观察图案列和主列时，有下图。
使用图p[k]和s[i]进行以下匹配
1=k j-1，那么两幅图加起来有什么效果呢？
从上图可以看出，如果s[i]和p[j]匹配不成功，p[k]和s[i]可以进行以下匹配：
s[i-k 1]，…，i-1]==p[j-k 1，…，j-1]==p[1，…，k-1]。
也就是说，如果s[i]和p[j]匹配不成功，则k必须满足以下条件，而不对主串执行最严格的回溯，并且在p[k]和s[i]中执行匹配：
p[1，…，k-1]==p[j-k 1，…，j-1]。
KMP算法的实现
KMP算法是对匹配模式匹配算法的改进，如果s[i]和p[j]匹配不成功，则不对主串进行指针回溯，而是对p[1，…，j-1
在s[i]和p[k]中进行下一轮的匹配。 其实现的最大问题是如何根据p[1，…，j-1]求出p[k]。
在KMP算法的安装中，使用辅助数组next[]，使用该数组在p[j]的匹配不成功的情况下，保存进行下一次匹配的k的值。也就是说，在s[i]和p[j]的匹配不成功的情况下，
在p[ next[j] ]中与s[i]进行以下匹配，设为k=next[j]。
要求解数组next[]，可以使用许多方法进行谷歌。 这里使用最简单的递归方法。
首先，假设next [0]=1，则在next[j]=k的情况下，p[0，…，j-1]==
p[j-k+1,…,j-1]。这时，若有p[k] = p[j] ，则p[0,….,k] = p[j-k+1,..,j-1,j]，从而就有next[j+1] = next[j] + 1 = k +1 .
若p[k] != p[j] ,可以看着模式串对自身进行匹配的问题，即当匹配失败的时候，k值如何确定，k = next [k] .
求数组next[ ]的实现如下：
/*
KMP进行模式匹配的辅助函数
模式串和主串匹配不成功时，下次和主串进行匹配的模式串的位置
*/
void continue_prefix_function(const char * p , int * next) {
int j ;
int k ;
next[0] = -1 ;
j = 0 ;
k = -1 ;
while(j < strlen(p) - 1) {
if( k == -1 || p[k] == p[j]) {
j ++ ;
k ++ ;
next[j] = k ;
}else {
k =next[k] ;
}
}
}
知道了当模式串和主串匹配不成功时，下一个和主串匹配的字符在模式串中的位置，在朴素的模式匹配的基础上很容易的写出KMP算法的代码如下：
/*运用KMP算法的字符串模式匹配
在主串和模式串匹配不成功时，不对主串指针进行回溯，
例如用next[j],来指定下一次和主串进行匹配的模式串的位置*/
int match_kmp(const char * s ,const char * p,intpos) {int next[11] ;int i =pos ;int j = 0;
continue_prefix_function(p,next) ;while(s[i] != ' ' && p[j] != ' ') {if(s[i] ==p[j]) {
i++;
j++;
}else{if(next[j] == -1) {
i++;
j= 0;
}else{
j=next[j] ;
}
}
}if(p[j] == ' ')return i -j ;else
return -1;
}
总结