kmp算法.txt

来自「里面包括了一些acm比赛是常用的函数」· 文本 代码 · 共 38 行

void getnext(char t[],int next[])
{
   //求模式t的next值并存入next数组中
	int i,j;
	i=1,j=0;
	next[1]=0;
	while(i<t[0])
	{
	    if(j==0||t[i]==t[j])
		{
		   i++;
		   j++;
		   next[i]=j;
		}
	    else j=next[j];	
	}
}

int kMp(char *s,char *t,int pos,int next[])
{
	//从s的第pos个字符开始找首次与串t相等的子串，next数组中为next函数的相关值
	int i,j;

	i=pos,j=1;

	while(i<=s[0]&&j<=t[0])
		if(j==0||s[i]==t[j])
		{
			t++;
			j++;
		}
		else   
		    j=next[j];
	if(j>t[0]) 
		return i-t[0];
	else return 0;
}