kmp.cpp

ACM经典算法ACM经典算法ACM经典算法

void get_nextval(const char *T, int next[])//求模式串T的next函数值存入next[]
{
	int j = 0, k = -1; 
	next[0] = -1; 
	while ( T[j/*+1*/] != '\0' ) 
	{ 
		if (k == -1 || T[j] == T[k]) 
		{ 
			++j; ++k; 
			if (T[j]!=T[k]) next[j] = k; 
			else next[j] = next[k]; 
		}
		else k = next[k]; 
	}    

}
int KMP(const char *Text,const char* Pattern)
{ 
	if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )// 
		return -1;//空指针或空串，返回-1。
	int len=0; 
	const char * c=Pattern; 
	while(*c++!='\0') ++len;
	int *next=new int[len+1];
	get_nextval(Pattern,next);
	int index=0,i=0,j=0; 
	while(Text[i]!='\0' && Pattern[j]!='\0' ) 
	{ 
		if(Text[i]== Pattern[j]) 
		{ 
			++i;
			++j; 
		} 
		else 
		{ 
			index += j-next[j]; 
			if(next[j]!=-1) 
				j=next[j];// 模式串向右移动
			else 
			{ 
				j=0; 
				++i; 
			} 
		}
	}
	delete []next;
	if(Pattern[j]=='\0') return index;
	else return -1;       
}