HDU 1711 Number Sequence（数列）

HDU 1711 Number Sequence（数列）

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

【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.	给定两串数组 : a[1], a[2], ...... , a[N], 和 b[1], b[2], ...... , b[M] (1 <= N <= 1000000, 1 <= M <= 10000)。你的任务是找到一个数字K使得a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]。如果存在多个K, 输出最小的那个。

【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].

输入的第一行是一个数字T 表示测试用例的数量。每个测试用例有三行。

第一行神两个数N和M (1 <= M <= 10000, 1 <= N <= 1000000)。

第二行有N个整数a[1], a[2], ...... , a[N]。

第三行有M个整数b[1], b[2], ...... , b[M]。

所有整数的范围都在 [-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.	对于每个测试用例，输出一行上述K值。如果K不存在，则输出-1.

【Sample Input - 输入样例】

【Sample Output - 输出样例】

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

-1

【题解】

KMP可解，初次匹配成功的时候结束即可。

【代码 C++】

 1 #include <cstdio>
 2 int a[1000005], b[10005];
 3 int aLen, bLen, next[10005] = { -1 };
 4 void setNext_b(){
 5     int i = 0, j = -1;
 6     while (i < bLen){
 7         if (j == -1 || b[i] == b[j]) next[++i] = ++j;
 8         else j = next[j];
 9     }
10 }
11 int fid(){
12     int i = 0, j = 0;
13     while (i < aLen){
14         if (j == -1 || a[i] == b[j]) ++i, ++j;
15         else j = next[j];
16         if (j == bLen) return i - j + 1;
17     }
18     return -1;
19 }
20 int main(){
21     int i, t;
22     scanf("%d", &t);
23     while (t--){
24         scanf("%d%d", &aLen, &bLen);
25         for (i = 0; i < aLen; ++i) scanf("%d", &a[i]);
26         for (i = 0; i < bLen; ++i) scanf("%d", &b[i]);
27         setNext_b();
28         printf("%d
", fid());
29     }
30     return 0;
31 }