Number Sequence

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

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

Source

kmp 基础

代码：

1 /*@kmp扩展@龚细军*/ 2 #include
       
         3 #include
        
          4 int aa[1000004],bb[10005]; 5 int next[10005]; 6 //依旧使用next数组 7 void get_next(int *pt,int len) 8 { 9     memset(next,0,sizeof(next));10     int i=0,j=-1;11     next[0]=-1;12     while(i

View Code

java代码：

1 import java.util.Scanner; 2  3  4 public class Main { 5      6     public static void main(String args []) 7     {   8         mt aa = new mt(); 9        Scanner reader =new Scanner(System.in);10        int test=reader.nextInt();11        while((test--)>0)12        {13           aa.lena=reader.nextInt();14           aa.lenb=reader.nextInt();15           aa.init(aa.lena+1, aa.lenb+1);16           for(int i=0;i

View Code

转载地址：http://fjxzx.baihongyu.com/

你可能感兴趣的文章