复习的时候觉得这一部分还是挺复杂的，就单独写了一个博客。如果有理解不对的地方，欢迎大家一起讨论。

---

---

1. 简单的模式匹配算法——BF模式匹配

串的模式匹配，是求模式串在主串中的位置。时间复杂度 O(n*m).

---

下面来看一下代码

int Index(SString S, SString T, int pos){
	int i = pos;
	int j = 1;
	while(i <= S.Len && j <= T.Len){
		if(S.ch[i] == T.ch[j]){
			i++;
			j++;
		}
		else{
			i = i - j + 2;
			j = 1;
		}
	}
	if(j > T.Len){
		return i - T.Len
	}
	else 
		return 0;
}

---

2. 改进的模式匹配算法——KMP算法

KMP的时间复杂度为 O(n+m)
KMP算法的改进在于：每当一趟匹配过程中出现比较的字符不相等时，不需要 i 回溯，二是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。

---

字符串的模式匹配——KMP算法：

（该计算过程中，我们先假设 next[j] 已知，后面详细介绍 next[j] 的计算过程）

next 值的计算思想过程：

用真前缀串和真后缀串进行比较
（简单说一下真前缀串和真后缀串吧）

对于字符串 abaab
它的前缀串为：a, ab, aba, abaa, abaab;
它的后缀串为：b, ab, aab, baab, abaab;
真前缀串：是指不包含它本身的前缀串，即 a, ab, aba, abaa;
真后缀串：是指不包含它本身的后缀串，即 b, ab, aab, baab;

next 值的手工计算过程：

nextval 值是对 next 值的改进

---

下面来看一下代码

//求next函数值的算法
void get_next(char T[], int next[]){
	int j = 1;
	int k = 0;
	next[1] = 0;
	while(j < T.Len){
		if(k == 0 || S.ch[j] == T.ch[k]){
			++i;
			++k;
			next[j] = k;
		}
		else
			k = next[k]
	}
}

//KMP的主体代码如下
int KMP(SString S, SString T, int pos){
	int i = pos;
	int j = 1;
	while( i <= S.Len && j <= T.Len){
		if(j == 0 || S.ch[i] == T.ch[j]){
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if(j > T.Len){
		return i - T.Len;
	}
	else
		return 0;
}

---