数据结构及算法之串的模式匹配算法

• 串的顺序存储表示：
• • BF算法：
  • KMP算法：

#define MAXSIZE   255;      //最大串长
typedef unsigned char SString[ MAXSIZE + 1 ];   //0号单元存放串的长度

int
Index_BF( SString S, SString T, int pos){
	//返回子串T在主串S中第pos个字符之后的位置。若不存在，则返回0
	//T非空，1<=pos<=StrLength(S)
	i = pos; j = 1;
	while( i <= S[0] && j <= T[0] ){
		if( S[i] == T[j] ){              //继续比较后续字符
			++i;
			++j; 
		}else{                          //指针后退重新开始匹配  
				i = i - ( j - 1 ) + 1;
				j = 1;
			}
	}
	if( j > T[0] )
		return i - T[0];
	else
		return 0;
}

int
Index_KMP( SString S, SString T, int pos){
	//返回子串T在主串S中第pos个字符之后的位置。若不存在，则返回0
	//T非空，1<=pos<=StrLength(S)
	i = pos; j = 1;
	while( i <= S[0] && j <= T[0] ){
		if( S[i] == T[j] ){              //继续比较后续字符
			++i;
			++j; 
		}
		else    j = next[j];            //模式串向右移动 				
	}
	if( j > T[0] )                      //匹配成功
		return i - T[0];
	else
		return 0;
}

KMP算法是在已知模式串的next函数值的基础上执行的，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可从分析定义出发用递推的方法求得next函数值。

void 
get_next( SString T, int next[] ){
	//求模式串T的next函数值并存入数组next。
	i = 1;  next[ 1 ] = 0;  j = 0;
	while( i < T[0] ){
		if( j == 0 || T[i] == T[j] ){
			++i;
			++j;
			next[ i ] = j;
		}else
		 j = next[ j ];
	}
}