【数据结构与算法】——字符串匹配篇

字符匹配算法是字符处理的一种基本操作，大致可分为【常规匹配算法】和【KMP算法】

【常规字符匹配算法】如下：

int index(char* s,char* t,int pos)
{
	int i = pos;
	int j = 1;
	while( i<strlen(s) && j< strlen(t))
	{
		if( s[i] == t[j] )
		{
			++i;
			++j;
		}
		else
		{
			i = i-j+1;
			j = 0;		
		}
	}

	if( j == strlen(t) )
		return i-strlen(t);
	else
		return -1;
}

这个算法在实际中经常使用，但有许多不必要的比较。算法复杂度为O(m*n)，但实际工作中效率近似O(m+n)，比较坏的情况较少出现。

【KMP算法】如下：

void get_next(char* t,int t_len,int *next)
{
	int i   = 0;
	int j   = -1;
	next[0] = -1;
	while( i<t_len )
	{
		if( j==-1 || t[i] == t[j] )
		{
			++i; ++j;
			if(i<t_len)
			{
				if(t[i] != t[j])
					next[i] = j;
				else
					next[i] = next[j];
			}
		}
		else
			j = next[j];
	}
}
int index_KMP(char* s,char *t, int pos)
{
	int s_len = strlen(s);
	int t_len = strlen(t);

	/*建立next数组记录跳步*/
	int *next = new int[t_len];
	get_next(t,t_len,next);

	/*开始匹配*/
	int i = pos;
	int j = 0;
	while( i<s_len && j<t_len )
	{
		if( j==-1 || s[i] == t[j] )
		{	++i; ++j;	}
		else
		{	j = next[j];}
	}

	delete[] next;

	/*返回结果*/
	if( j == t_len )
		return i-t_len;
	else
		return -1;
};

    其中具体的匹配算法和常规算法十分类似，但是多了一个next数据来记录跳步，这样可以减少大量不必要的比较操作。上面的KMP算法采用的是一种改进的KMP算法，避免了KMP算法有时候做多余比较的一些情况（参见严蔚敏《数据结构》）。KMP算法将算法的时间复杂度降到了O(m+n)，但也用到了O(n)的辅助空间，一般来说匹配的模式串都不会太长，所以一般辅助空间都是很小的，所以空间耗费是不需要多担心的。但是new操作建立next数据却是很费时间的，尤其是大量频繁调用KMP匹配算法的时候，这导致KMP可能比常规算法还慢，解决办法是判断模式串长度，一般情况下，都采用堆分配，最终算法如下：

void get_next(char* t,int t_len,int *next)
{
	int i   = 0;
	int j   = -1;
	next[0] = -1;
	while( i<t_len )
	{
		if( j==-1 || t[i] == t[j] )
		{
			++i; ++j;
			if(i<t_len)
			{
				if(t[i] != t[j])
					next[i] = j;
				else
					next[i] = next[j];
			}
		}
		else
			j = next[j];
	}
};

int index_KMP_large(char* s,int s_len,char *t,int t_len, int pos)
{
	/*建立next数组记录跳步*/
	int *next = new int[t_len];
	get_next(t,t_len,next);

	/*开始匹配*/
	int i = pos;
	int j = 0;
	while( i<s_len && j<t_len )
	{
		if( j==-1 || s[i] == t[j] )
		{	++i; ++j;	}
		else
		{	j = next[j];}
	}

	delete[] next;

	/*返回结果*/
	if( j == t_len )
		return i-t_len;
	else
		return -1;
};

int index_KMP_fast(char* s,int s_len,char *t,int t_len, int pos)
{
	/*建立next数组记录跳步*/
	int next[256]; 
	get_next(t,t_len,next);

	/*开始匹配*/
	int i = pos;
	int j = 0;
	while( i<s_len && j<t_len )
	{
		if( j==-1 || s[i] == t[j] )
		{	++i; ++j;	}
		else
		{	j = next[j];}
	}

	/*返回结果*/
	if( j == t_len )
		return i-t_len;
	else
		return -1;
};

int index_tmp(char *s, char *t, int pos)
{
	int s_len = strlen(s);
	int t_len = strlen(t);
	int index = -1;

	if(t_len > s_len)
		return index;

	if(t_len < 256 )
		index = index_KMP_fast(s,s_len,t,t_len,pos);
	else
		index = index_KMP_large(s,s_len,t,t_len,pos);

	return index;
};

上述的写法，使得整个算法看山去，特别长而繁琐。你可以把代码写得更加简洁：

void get_next(char* t,int t_len,int *next)
{
	int i   = 0;
	int j   = -1;
	next[0] = -1;
	while( i<t_len )
	{
		if( j==-1 || t[i] == t[j] )
		{
			++i; ++j;
			if(i<t_len)
			{
				if(t[i] != t[j])
					next[i] = j;
				else
					next[i] = next[j];
			}
		}
		else
			j = next[j];
	}
}
int index_op(char *s, char *t, int pos)
{
	int s_len = strlen(s);
	int t_len = strlen(t);
	int flag  = 0;

	if( t_len > s_len )
		return -1;
	
	int *next = NULL;
	if( t_len <256 )
	{
		int tmp[256];
		next = tmp;
	}
	else
	{
		next = new int[t_len];
		flag = 1;
	}
	get_next(t,t_len,next);

	/*开始匹配*/
	int i = pos;
	int j = 0;
	while( i<s_len && j<t_len )
	{
		if( j==-1 || s[i] == t[j] )
		{	++i; ++j;	}
		else
		{	j = next[j];}
	}

	if( flag==1 )
		delete []next;

	/*返回结果*/
	if( j == t_len )
		return i-t_len;
	else
		return -1;
};

    另外，最后提一句，要理解KMP算法，按照一般课本的方式显得特别繁琐，容易绕晕，其实KMP算法的本质就是模拟DFA(有限状态自动机)，从自动机的角度理解KMP其实才是最简洁直观的。