【数据结构】 串的模式匹配算法KMP

/*
==========================================================================================
					串的模式匹配算法
				By~fanxingzju	2014.04.27
1.Judge(T,pos,num)函数
判断String开头的num个元素组成的字符串与pos位置前的num个元素组成的字符串是否相同
2.get_next_my(T,next[])函数
根据给定的串获取KMP算法中使用的next[]数组
3.Index_KMP(S,T,pos)
串模式匹配的KMP算法
4.PrintNext(T)
打印next[]数组
5.get_next()
根据给定的串获取KMP算法中使用的next[]数组
其余的函数在“【数据结构】 串的基本操作”中已经存在
==========================================================================================
说明：
1.get_next_my()是参照【数据结构】中对KMP的介绍自己写的函数
2.get_next()是对【数据结构】中给出的函数略微修改得到的
3.由于以前版本的Index()函数不太适合使用KMP算法，这里对Index()函数进行了较大改动
4.【算法导论】中串的下标与这里略有不同，它用[0]位置来储存串的长度，这里用''判断串是否结束
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	char *ch;
	int length;
}HString;

bool InitString(HString &T)
{
	T.ch = NULL;
	T.length = 0;
	return true;
}

bool StrAssign(HString &T,char *chars)
{
	if (T.ch)
	{
		delete[] T.ch;
	}

	char *ctemp = chars;
	T.length = 0;

	while(*ctemp)
	{
		++T.length;
		++ctemp;
	}

	T.ch = new char[T.length + 1];
	if (!T.ch)
	{
		printf("StrAssign()函数执行，内存分配失败，程序即将退出n");
		system("pause");
		exit(-1);
	}

	char *tmp = T.ch;
	while(*chars)
	{
		*tmp++ = *chars++;
	}
	*tmp = '';

	printf("StrAssign()函数执行，串T生成成功n");
	return true;
}

bool PrintString(HString T)
{
	if (!T.ch)
	{
		printf("PrintString()函数执行，串不存在n");
		return false;
	}
	else
	{
		printf("PrintString()函数执行，串的长度为 %d ，打印结果如下：",T.length);
		while(*T.ch)
		{
			printf("%c",*T.ch++);
		}
		printf("n");
		return true;
	}
}

bool DestoryString(HString &Str)
{
	if (Str.ch)
	{
		delete[] Str.ch;
	}
	Str.ch = NULL;
	Str.length = 0;
	printf("DestoryString()函数执行，串销毁成功n");
	return true;
}

// 当前正在判断的元素是HString的第pos个元素
// 判断String开头的num个元素组成的字符串与pos位置前的num个元素组成的字符串是否相同
bool Judge(HString T,int pos,int num)
{
	if ((pos > T.length)||(pos < 1))
	{
		printf("Judge()函数执行，pos参数错误，pos = %dn",pos);
		system("pause");
		exit(-2);
	}
	if ((num < 1)||(num > pos - 2))
	{
		printf("Judge()函数执行，num参数错误，num = %dn",num);
		system("pause");
		exit(-2);
	}
	bool flag = true;
	for (int i = 0; i != num; ++i)
	{
		if (*(T.ch + i) != *(T.ch + pos - num -1 + i))
		{
			flag = false;
			break;
		}
	}
	return flag;
}

bool get_next_my(HString T,int next[])
{
	next[0] = 0;
	for (int index = 1; index != T.length; ++index)
	{
		bool flag = true;
		for (int len = index - 1; len != 0; --len)
		{
			if (Judge(T,index + 1,len))
			{
				next[index] = len +1;
				flag = false;
				break;
			}
		}
		if (flag)
		{
			next[index] = 1;
		}
	}
	return true;
}

bool get_next(HString T,int next[])
{
	int i = 1,j = 0;
	next[0] = 0;
	while(i < T.length)
	{
		if ((0 == j)||(*(T.ch + i - 1) == *(T.ch + j - 1)))
		{
			++i;
			++j;
			next[i-1] = j;
		} 
		else
		{
			j = next[j-1];
		}
	}
	return true;
}

bool PrintNext(HString T)
{
	int *next = new int[T.length];
	if (NULL == next)
	{
		printf("PrintNext()函数执行，内存分配失败，程序即将退出n");
		system("pause");
		exit(-1);
	}
	//get_next(T,next);
	get_next_my(T,next);
	printf("串对应对应的next[]数组如下：n");
	for(int i = 0; i != T.length; ++i)
	{
		if (i != T.length - 1)
		{
			printf("%d ",next[i]);
		} 
		else
		{
			printf("%dn",next[i]);
		}
	}
	delete[] next;
	return true;
}


//9.Index(S,pos)
int Index_KMP(HString Str,HString T,int pos)
{
	if (!Str.ch||!T.ch||(0 == T.length))
	{
		printf("Index()函数执行，串不存在或为空串，程序即将退出n");
		system("pause");
		exit(-1);
	}
	if ((pos < 1)||(pos > Str.length))
	{
		printf("Index()函数执行，pos参数错误n");
		return 0;
	}
	int *next = new int[T.length];
	if (NULL == next)
	{
		printf("Index_KMP()函数执行，内存分配失败，程序即将退出n");
		system("pause");
		exit(-1);
	}
	get_next(T,next);
	int j = 0;
	for (int i = pos - 1; i != Str.length - T.length + 1; )
	{
		if (*(Str.ch + i) == *(T.ch + j))
		{
			while(j != T.length)
			{
				if (*(Str.ch + i) != *(T.ch + j))
				{
					j = next[j];
					if (0 == j)
					{
						++i;
					} 
					else
					{
						--j;
					}
					// 将上面一段换成 j = 0;就是普通Index算法
					// next[j]等于零时，直接从主串的下一个位置开始于字串比较
					// next[j]非零时，将主串现在位置的元素与字串的第next[j]个元素比较
					break;
				}
				else
				{
					++i;
					++j;
				}
			}
			if (j == T.length)
			{
				printf("Index()函数执行，主串S第%d个字符之后第一次出现与串T相同的字串的位置为：%dn",i - T.length + 1);
				delete[] next;
				return (i - T.length + 1);
			}
		} 
		else
		{
			++i;
		}
	}
	delete[] next;
	printf("Index()函数执行，主串第%d个字符之后未找到与串T相同的字串n",pos);
	return 0;
}

int main()
{
	HString T1,T2,T3;
	InitString(T1);
	InitString(T2);
	InitString(T3);
	char *tmp1 = "abaabcac";
	char *tmp2 = "aaaac";
	char *tmp3 = "abc";
	StrAssign(T1,tmp1);
	StrAssign(T2,tmp2);
	StrAssign(T3,tmp3);
	PrintString(T1);
	PrintNext(T1);
	PrintString(T2);
	PrintNext(T2);

	PrintString(T3);
	Index_KMP(T1,T3,2);

	DestoryString(T1);
	DestoryString(T2);
	DestoryString(T3);
	system("pause");
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!