串的模式匹配

• 1 简单的模式匹配算法
• 2 KMP算法
• 3 KMP算法改进
• 4 时间复杂度比较

1 简单的模式匹配算法

思想： 将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串或所有子串都不匹配为止。

具体代码展示：
1）串的初始化工作

#include<stdio.h>
#define MAXLEN 255  //预定义最大串长

typedef struct {
	char ch[MAXLEN];//每一个分量存储一个字符
	int length;//串的实际长度
}SString;

// 字符串下标从1开始记录，将ch[0]设置为‘\0’ 
SString createString() {
	SString str;
	str.ch[0] = '\0';
	str.length = 0;
	return str;
}

//赋值操作
void StrAssign(SString& S, char chars[])//生成串S
{
	int i = 0;
	while (chars[i] != '\0')
	{
		//第一个位置不用
		S.ch[i+1] = chars[i];//将字符串常量的值赋值给S
		i++;
	}
	S.length = i+1;
}

//打印串
void PrintString(SString S) {
	if (S.length == 0) {
		printf_s("当前串为空");
	}
	else {
		for (int i = 1; i < S.length; i++) {
			printf_s("%c", S.ch[i]);
		}
		printf_s("\n");
	}
}

2）简单模式匹配算法实现

int Index(SString S, SString T) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length) {
		//相等则指针+1
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;//主串指针退回到当前指针的下一个位置
			j = 1;//模式串指针退回到第一个位置
		}
		//放在这里判断是为了返回第一个匹配的子串位置，
		//T的长度是实际长度+废弃的第一个位置长度，所以这里减一
		//说明匹配完成，指向T的最后一个元素的下一个位置
		if (j > T.length - 1) {
			return i - T.length + 1;
		}
	}
	return 0;
}

3）主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "aaabaabcaabdabacaabc" };
	char ch2[] = { "aabc" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法：\n");
	printf_s("子串在主串位置为：%d", Index(S, T));
}

4）结果展示

注意：子串匹配的是在主串中首次出现的，在所给例子中，子串出现了两次，但是记录的位置是第一次出现的位置。

2 KMP算法

简单模式匹配算法： 当子串的某一字符与主串对应的字符不匹配时，主串的指针会回溯到扫描第一个位置的下一个位置，子串的指针也会回溯到第一个位置，然后重新匹配。但是没必要去比较后面的某些位置，因为在主串中，匹配失败的那个字符肯定不是b，所以下一次指针位置应该为3，而不是2，如下图所示。

所以，也就引出了KMP算法，即将子串的指针位置组成一个next数组，这样就极大地减少比较的次数。next[i]的含义是在第i个字符与主串发生失配时，则跳到字串的next[i]位置重新与主串当前位置进行比较。
比如主串为：abacaabefc，子串为aab，则next数组为0，1，2。手算可以推出来的，并且要注意的是next[1]肯定等于0，为什么？因为当子串的第一个字符匹配失败时，那肯定转到第二个位置继续匹配。

具体代码展示：

1）next数组代码求解过程如下（不作过多讲解）

//求next数组
//next[1]为0，next[2]为1
void get_next(SString T, int next[]) {
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}

2）KMP算法实现

int Index_KMP(SString S, SString T, int next[]) {
	int i = 1, j = 1;
	while (i <= S.length&&j <= T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];//确定模式串的指针位置
		}
		//匹配成功
		if (j > T.length-1) {
			return i - T.length+1;
		}
	}
	return 0;
}

3）主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "abacaabefc" };
	char ch2[] = { "aab" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法：\n");
	printf_s("子串在主串位置为：%d", Index(S, T));
	printf_s("\n----------------------------\n");
    printf_s("KMP算法：\n");
	int next[10] = { -1 };//第一个值弃用
	get_next(T, next);
	printf_s("next数组元素为：");
	for (int i = 1; i < T.length;i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为：%d", Index_KMP(S, T,next));
}

4）运行结果

3 KMP算法改进

KMP算法问题： 当子串’aaaab’与’aaabaaaab’匹配时，当i=4，j=4时，子串与主串匹配失败，用之前的next数组还需要和S₄和P₃、S₄和P₂、S₄和P₁比较，显然没有意义。问题就出在P_j=P_next[j]上，因为当P_j≠S_j时，下次匹配的必然是P_next[j]和S_j比较，如果P_j=P_next[j]，相当于重复匹配相同字符，那怎么办，可以继续递归，将next[j]修改为next[next[j]]直至两者不相等为止。

具体代码实现：
1）next数组优化

//求next数组优化，匹配失败的那个位置的字符肯定不是当前匹配子串的字符
void get_nextval(SString T, int nextval[]) {
	int i = 1, j = 0;
	nextval[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			if (T.ch[i] != T.ch[j]) {
				nextval[i] = j;
			}
			else {
				nextval[i] = nextval[j];
			}
		}
		else {
			j = nextval[j];
		}
	}
}

2）主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "aaabaaaab" };
	char ch2[] = { "aaaab" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法：\n");
	printf_s("子串在主串位置为：%d", Index(S, T));
	printf_s("\n----------------------------\n");
	printf_s("KMP算法：\n");
	int next[10] = { -1 };//第一个值弃用
	get_next(T, next);
	printf_s("next数组元素为：");
	for (int i = 1; i < T.length;i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为：%d", Index_KMP(S, T,next));
	printf_s("\n----------------------------\n");
	get_nextval(T, next);
	printf_s("nextval数组元素为：");
	for (int i = 1; i < T.length; i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为：%d\n", Index_KMP(S, T, next));
	return 0;
}

3）运行结果

4 时间复杂度比较

• 简单模式匹配算法： 最坏复杂度为O(mn)
• KMP算法： 最坏时间复杂度为O(m+n)
  其中求next数组时间复杂度为O(m)
  模式匹配过程中最坏时间复杂度为O(n)