Number Sequence

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

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
5
2 1 2 3 1 2 3 1 3 2 1 2
2 3 1 3
5
2 1 2 3 1 2 3 1 3 2 1 2
2 3 2 1

Sample Output

6
-1

初学KMP，水一发模版题

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 
13 using namespace std;
14 const int maxn = 1000010;
15 int na, nb;
16 int a[maxn];
17 int b[maxn];
18 int pre[maxn];
19 
20 void getpre(int *b, int *pre) {
21     int j, k;
22     pre[0] = -1;
23     j = 0;
24     k = -1;
25     while(j < nb - 1) {
26         if(k == -1 || b[j] == b[k]) {//匹配
27             j++;
28             k++;
29             pre[j] = k;
30         }
31         else {  //b[j] != b[k]
32             k = pre[k];
33         }
34     }
35 }
36 
37 int kmp() {
38     int i = 0;
39     int j = 0;
40     getpre(b, pre);
41     while(i < na) {
42         if(j == -1 || a[i] == b[j]) {
43             i++;
44             j++;
45         }
46         else {
47             j = pre[j];
48         }
49         if(j == nb) {
50             return i - nb + 1;
51         }
52     }
53     return -1;
54 }
55 
56 int main() {
57     int T;
58     scanf("%d", &T);
59     while(T--) {
60         scanf("%d %d", &na, &nb);
61         for(int i = 0; i < na; i++) {
62             scanf("%d", &a[i]);
63         }
64         for(int i = 0; i < nb; i++) {
65             scanf("%d", &b[i]);
66         }
67         printf("%d
", kmp());
68     }
69     return 0;
70 }

本题还可以用hash做，效率与kmp差距不大。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <list>
12 #include <vector>
13 
14 using namespace std;
15 
16 typedef unsigned long long ull;
17 const int B = 100007;
18 const int maxn = 1000010;
19 int a[maxn], b[maxn];
20 int na, nb;
21 
22 ull quickmul(int x, int n) {
23     ull ans = 1;
24     ull t = x;
25     while(n) {
26         if(n & 1) {
27             ans = (ans * t);
28         }
29         t = t * t;
30         n >>= 1;
31     }
32     return ans;
33 }
34 
35 int contain() {
36     if(na > nb) {
37         return false;
38     }
39     ull t = quickmul(B, na);
40     ull ah = 0, bh = 0;
41     for(int i = 0; i < na; i++) {
42         ah = ah * B + a[i];
43     }
44     for(int i = 0; i < na; i++) {
45         bh = bh * B + b[i];
46     }
47     for(int i = 0; i + na <= nb; i++) {
48         if(ah == bh) {
49             return i + 1;
50         }
51         if(i + na < nb) {
52             bh = bh * B + b[i+na] - b[i] * t;
53         }
54     }
55     return -1;
56 }
57 int main() {
58     // freopen("in", "r", stdin);
59     int T;
60     scanf("%d", &T);
61     while(T--) {
62         scanf("%d %d", &nb, &na);
63         for(int i = 0; i < nb; i++) {
64             scanf("%d", &b[i]);
65         }
66         for(int i = 0; i < na; i++) {
67             scanf("%d", &a[i]);
68         }
69         printf("%d
", contain());
70     }
71     return 0;
72 }