int* bctable(char* p)
{
	int *bc=new int[CHAR_MAX];
	int p_len=strlen(p);
	for(int i=0;i<CHAR_MAX;i++) bc[i]=-1;
	for(int i=0;i<p_len-1;i++) bc[p[i]]=i;
	return bc;
}

int* mstable(char* p)
{
	int n = strlen(p); int* ms = new int[n];
	ms[n-1] = n; //串与自身一定匹配
	int lower = n-1, upper = n-1;
	for(int i=upper-1; i>=0; i--)
	{
		if(i>lower && ms[n-upper+i-1]<=i-lower)
			ms[i] = ms[n-upper+i-1];
		else
		{
			upper = i; lower = min(upper, lower);
			while(lower>=0 && p[lower] == p[n-upper+lower-1]) lower--;
			ms[i] = upper - lower;
		}
	}
	return ms;
}

int* gstable(char *p)
{
	int *ms=mstable(p);
	int n = strlen(p); int* gs = new int[n];
	for(int i=0; i<n; i++) gs[i] = n;
	for(int i=0, j=n-1; j>=0; j--)
	{
		if(j+1==ms[j])
			while(i<n-j-1)
				gs[i++]=n-j-1;
			
	}
	for(int i=0; i<n-1; i++)
		gs[n-ms[i]-1] = n-i-1;
	delete [] ms;
	return gs;
}

int BMSearch(char* p, char* t)
{
	int* bc = bctable(p); int* gs = gstable(p);
	int i = 0, m = strlen(p), n = strlen(t);
	while(i<=n-m)
	{
		int k = m-1;
		while(t[i+k] == p[k])
			if(--k<0)
				break;
		if(k<0)
			break;
		else
		{
			i += max(gs[k], k-bc[t[i+k]]);
		}
	}
	delete [] bc; delete [] gs;
	if(i<=n-m) return i;
	else return -1; //匹配失败
}