模式匹配：

假设有两个字符串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])时）  以上过程图摘自：http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

下面给出实现代码：

/*——————暴力匹配——————注意const的用法，去掉之后编译会出现waring，看看*/ #include 
     
      #include 
      
       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;} 
      
     

算法分析：

我们可以看出，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:如果不明白这个函数的意义，请看此链接：http://www.java3z.com/cwbwebhome/article/article19/re022.html?id=3731）

*模式失配函数：

定义模式失配函数为：next[]。

如果说next[j] = k,表明如果s[i] != p[j]的时候，j应该回溯到的pattern字符串的位置！                          

举例说明：

   j   0  1  2  3   4   5  6   7  8  9  10

p[j] A  B  R  A  C  A  D  A  B  R  A

      next[j]  -1  0  0   0   1  0   1  0   1  2  3 

默认情况下next[0] = -1，这是一个标示符，因为如果说next[j] = -1 即说明pattern的第一个字符就失配了，此时j不需要回溯，单纯的设置为-1

根据失配函数的定义，得到如下模式匹配规则：

1.如果出现了形如s[i-j]s[i-j+1]...s[i-1] = p[0]p[1]....p[j-1]且s[i] != p[j]的部分匹配，那么，若j != -1 则下一次模式匹配时，比较失配字符s[i]和p[next[j]]

2.若j = -1 ，则继续比较s[i+1]和p[0]，代码如下:

/*-----------------------------------算法4.6/4.7-------------------------------------------------------------KMP------------------------------------------------------------------------------------------------------*/ #include 
    
     #include 
     
      #define maxn 10005int next[maxn];int KMP(char *s,char *p,int start_pos){	int i = start_pos,j = 0;		while(i < strlen(s)){		if(s[i] == p[j] || j == -1){			++i;			++j;		}		else 			j = next[j];		if(j  == strlen(p))			return start_pos + (i - j);	}	return -1;}void GetNext(char *s){	int j = 0, k = -1;		next[0] = -1;	while(s[j] != '\0'){		if(s[j] == s[k] || k == -1){			j++;			k++;			next[j] = k;		} 		else			k = next[k];	}}int main(){	char s[maxn] = {0};	char p[maxn] = {0};		scanf("%s",s);	scanf("%s",p);	int start_pos = 0;	GetNext(p);	int ans = KMP(s,p,start_pos);	printf("%d\n",ans);	return 0;}
     
    

__________________________________________________________________________________________________________________________________________________________

会发现，next和KMP的写法很相近。

其实next就是把pat自己和自己进行模式匹配。

具体的证明————严蔚敏老师的《数据结构》有讲，而且很详细。