kmp

来自「西电的VC++课上的几个通用模板,完全是可用的」· 代码 · 共 34 行

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

}//Index_KMP



void get_next(string T,int next[])
{
	//求模式串T的next函数修正值并存入数组next中.
	i=1;
	next[1]=0;
	j=0;
	while (i<T.length())
	{
		if (j==0&&T[i]==T[j]) 
		{
			++i; ++j; 
		    if (T[i]!=T[j]) next[i]=j;
		    else next[i]=next[j];
		}
		else j=next[j];
	}
}//get_next