（43）5.10数据结构第四章串（串的模式匹配）

1.朴素模式的匹配算法

#define MAXLEM 255
typedef struct
{
	char ch[MAXLEM];
	int length;
}SString;
//1.朴素模式匹配
int Index(SString S, SString T)
{
	int i = 1; int j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (S.ch[i] == T.ch[i])
		{
			++i;
			++j;             //继续比较后继字符
		}
		else
		{
			i = i - j + 2;
			j = 1;          //指针后退重新开始匹配
		}
		if (j > T.length)
			return i - T.length;
		else
			return 0;
	}
}
//时间复杂度O（nm）

2.KMP算法

2.1KMP算法

//2.KMP算法
int Index(SString S, SString T，int next[])
{
	int i = 1; int j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (j==0||S.ch[i] == T.ch[i])
		{
			++i;
			++j;             //继续比较后继字符
		}
		else
		{
			i = i - j + 2;
			j = 1;          //指针后退重新开始匹配
		}
		if (j > T.length)
			return i - T.length;
		else
			return 0;
	}
}
//时间复杂度O(n+m)

过程

2.2KMP算法进一步优化

//3.KMP算法优化
int Index(SString S, SString T，int next[])
{
	int i = 1; int j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[i])
		{
			++i; 
			++j;                //继续比较后继字符
		}
		else
		{
			j = next[j];        //模式串向右移动
		}
		if (j > T.length)
			return i - T.length;//匹配成功
		else
			return 0;
	}
}

2.3KMP算法--求next数组

3.求nextval数组