const int maxn=1e4+10;
int nex[maxn];//记录的是前缀和后缀最大公共部分的下一位坐标，由数组前后缀最大公共长度右移一位得出 
char p[maxn],s[maxn];
void init()
{
	fill(nex,nex+maxn,0);
	//fill(p,p+maxn,'');
}
void getnex()
{
	int i=-1,j=0;//因为求next数组是由前缀和后缀共同求出，切next[1]没求出，所以i要从-1开始，j从零开始 
	nex[0]=-1;
	int len=strlen(p);
	while(j<len-1)
	{//i=-1表示不存在公共前缀和后缀 
		if(i==-1||p[i]==p[j])//i==-1说明如果第j位匹配不到，则让i=-1,是j+1的位置与0匹配。 
		{
			i++;
			j++;
			nex[j]=i;			
		}
		else 
		{
			i=nex[i];
		}				
	}		
}

int kmp()
{
	int i=0,j=0;
	int slen=strlen(s);
	int plen=strlen(p);
	while(j<plen&&i<slen)
	{//j=-1表示，s串和p串i,j之前的不存在能匹配的 
		if(j==-1||s[i]==p[j])
		{
			i++;
			j++;
		}
		else
		{
			j=nex[j];
		}	
	}
	if(j==plen)
	return i-j;
	else
	return -1;	
}