1711 Number Sequence（kmp）

Number Sequence

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 90 Accepted Submission(s) : 57

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

HDU 2007-Spring Programming Contest

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <string>
 5 using namespace std;
 6 int a[1000005];
 7 int b[10005];
 8 int nxt[10005];
 9 int n, m;
10 int kmp()
11 {
12     int i, j;
13     j = 0;
14     for (i = 1; i <= n; i++)
15     {
16         while (j&&b[j + 1] != a[i]) j = nxt[j];
17         if (a[i] == b[j+1])
18         {
19             j++;
20         }
21         if (j == m)
22         {
23             return i - m + 1;
24         }
25     }
26     return -1;
27 }
28 int main()
29 {
30     int t;
31     cin >> t;
32     while (t--)
33     {
34         cin >> n >> m;
35         int i, j;
36         for (i = 1; i <= n; i++)
37         {
38             cin >> a[i];
39         }
40         for (i = 1; i <= m; i++)
41         {
42             cin >> b[i];
43         }
44         j = 0;
45         for (i = 2; i <= m; i++)
46         {
47             while (j&&b[j + 1] != b[i]) j = nxt[j];
48             if (b[j + 1] == b[i]) j++;
49             nxt[i] = j;
50         }
51         int f = kmp();
52         cout << f << endl;
53     }
54     return 0;
55 }

#include <iostream>#include <algorithm>#include <cstring>#include <string>using namespace std;int a[1000005];int b[10005];int nxt[10005];int n, m;int kmp(){int i, j;j = 0;for (i = 1; i <= n; i++){while (j&&b[j + 1] != a[i]) j = nxt[j];if (a[i] == b[j+1]){j++;}if (j == m){return i - m + 1;}}return -1;}int main(){int t;cin >> t;while (t--){cin >> n >> m;int i, j;for (i = 1; i <= n; i++){cin >> a[i];}for (i = 1; i <= m; i++){cin >> b[i];}j = 0;for (i = 2; i <= m; i++){while (j&&b[j + 1] != b[i]) j = nxt[j];if (b[j + 1] == b[i]) j++;nxt[i] = j;}int f = kmp();cout << f << endl;}return 0;}