串的模式匹配算法

子串的定位操作通常称做串的模式匹配(T为模式串) ,是各种串处理系统中最重要的操作之一.

简单算法:

int index(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 +2; j =1;}
	} 
	if(j >T[0]) return i-T[0];
	else return 0;
}//index

KMP算法:

int index_KMP(SString S, SString T, int pos) {
	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中,T非空,1<= pos <= StrLength(S)
	i = pos; j = 1;
	while(i <= S{0] && j <= T[0]) {
		if( j == 0 || S[i] == T[j]) {++i; ++j;}
		else j = next[j];
	}
	if(j > T[0]) return i - T[0];
	else return 0;
}//index_KMP

KMP算法中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[j] = j;}
		else j = next[j];
	}
}//get_next

next函数修正值算法:

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

第一次感受到算法的高深的微妙,感到非常的神奇,也感叹发明这个算法的D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 相信自己会努力成为了不起的人!