private int[] pre_kmp(String x)
{
	int i, j;
	int m = x.length()-1;
	int kmp_next[] = new int[m+1];

	i = 0;
	j = -1;
	kmp_next[0] = -1;
	while (i < m)
	{
		while (j > -1 && x.charAt(i) != x.charAt(j))
			j = kmp_next[j];
		i++;
		j++;
		if (x.charAt(i) == x.charAt(j))
			kmp_next[i] = kmp_next[j];
		else
			kmp_next[i] = j;
	}
	return kmp_next;
}