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 
      
       #include 
       
        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;}