int *COMPUTE_PREFIX_FUNCTION(char *P)
{
	int m = strlen(P);
	int *pai = new int[m+1];
	pai[0] = -1;
	int k = -1;
	for(int q = 1; q < m; q++)
	{
		while(k>-1&&P[k+1]!=P[q])
			k = pai[k];
		if(P[k+1]==P[q])
			k++;
		pai[q] = k;
	}
	return pai;
}
int KMP_MATCHER(char *T, char *P)
{
	int n = strlen(T);
	int m = strlen(P);
	int *pai = COMPUTE_PREFIX_FUNCTION(P);
	int q = -1, count = 0;
	for(int i = 0; i < n; i++)
	{
		while(q>-1&&P[q+1]!=T[i]) 
			q = pai[q];
		if(P[q+1]==T[i])
			q++;
		if(q == m-1)
		{
			count++;
			q = pai[q];
		}
	}
	delete[] pai;
	return count;
}