HDU 1711 Number Sequence KMP題解

HDU 1711 Number Sequence KMP題解

KMP查找整數數列，不是查找字符串。

原理是一樣的，不過把字符串轉換為數列，其他基本上是一樣的。

#include 
#include 

const int MAX_N = 1000001;
const int MAX_M = 10001;
int strN[MAX_N], strM[MAX_M], next[MAX_M], N, M;

void getNext()
{
	memset(next, 0, sizeof(int) * M);
	for (int i = 1, j = 0; i < M; )
	{
		if (strM[i] == strM[j]) next[i++] = ++j;
		else if (j > 0) j = next[j-1];
		else i++;
	}
}

int kmpSearch()
{
	int i = 0, j = 0;
	for ( ; M-j <= N-i && j < M; )
	{
		if (strN[i] == strM[j]) i++, j++;
		else if (j > 0) j = next[j-1];
		else i++;
	}
	if (j == M) return i-M+1;//注意題意從1開始
	return -1;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &N, &M);
		for (int i = 0; i < N; i++)
		{
			scanf("%d", strN+i);
		}
		for (int i = 0; i < M; i++)
		{
			scanf("%d", strM+i);
		}
		getNext();
		printf("%d\n", kmpSearch());
	}
	return 0;
}