HDU1711Number Sequence KMP

Number Sequence

                                                                                                      Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
                                                                                                                                 Total Submission(s): 3036    Accepted Submission(s): 1356

Problem Description

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

 

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

 

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

 

Sample Input

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

 

Sample Output

6
-1

 　　题目只是将字符串匹配变成了整型数据的匹配，其思想还是一样的，前面没有看见每个数据的范围是-1000000 - 1000000，直接用gets(  )进行读取，后果可想而知，RE了，当然就是数组开的不够大罗。当然如果系统能够让我开个2000000000000的数组应该也行吧，哦，那可能又会超时。

　　代码如下：

#include <stdio.h>
#include <string.h>

int o[1000010], s[10010];

int M, N;

void getnext( int *s, int *next )
{
	int k= 1, j= 0;
	while( k< M )
	{
		if( j== 0|| s[k]== s[j] )
		{
			++j, ++k;
			if( s[k]== s[j] )
			{
				next[k]= next[j];
			}
			else
			{
				next[k]= j;
			}
		}
		else
		{
			j= next[j];
		}
	}
}

int kmp( int *o, int *s, int *next )
{
	int k= 0, j= 0;
	while( k<= N&& j<= M )
	{
		if( j== 0|| o[k]== s[j] )
		{
			++j, ++k;
		}
		else
		{
			j= next[j];
		}
	}
	if( j> M )
	{
		return k- M;
	}
	else
	{
		return -1;
	}
}

int main(  )
{
	int T, next[20010];
	scanf( "%d" ,&T );
	while( T-- )
	{
		scanf( "%d %d", &N, &M );
		for( int i= 1; i<= N; ++i )
		{
			scanf( "%d", &o[i] );
		}
		for( int i= 1; i<= M; ++i )
		{
			scanf( "%d", &s[i] );
		}
		getnext( s, next );
		int ans= kmp( o, s, next );
		if( ans )
		{
			printf( "%d\n", kmp( o, s, next ) );
		}
	}
	return 0;
}