Number Sequence (HDU-1711)
题面
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.
输入
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].
输出
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
样例输入
12
213 5
31 2 1 2 3 1 2 3 1 3 2 1 2
41 2 3 1 3
513 5
61 2 1 2 3 1 2 3 1 3 2 1 2
71 2 3 2 1
样例输出
16
2-1
提示
无
思路
KMP模板题
代码
1int s[mxn], t[mxn];
2int nxt[mxn];
3
4void getnxt(int* t, int m)
5{
6 int i = 0, j = -1; nxt[0] = -1;
7 while (i < m)
8 {
9 if (j == -1 || t[i] == t[j]) {
10 i++, j++;
11 // if (t[i] == t[j])
12 // nxt[i] = nxt[j]; // next数组优化
13 // else
14 nxt[i] = j;
15 } else
16 j = nxt[j];
17 }
18}
19
20int KMP(int* s, int* t, int n, int m)
21{
22 int i = 0, j = 0, ans = 0;
23 while (i < n)
24 {
25 if (j == -1 || s[i] == t[j]) {
26 i++, j++;
27 if (j >= m) { // 匹配
28 // ans++;
29 // j = nxt[j];
30 return i-j;
31 }
32 } else
33 j = nxt[j];
34 }
35 // return ans;
36 return -1;
37}
38
39int main()
40{
41 int T; scanf("%d", &T);
42 while(T--)
43 {
44 int n, m;
45 scanf("%d %d", &n, &m);
46 for(int i=0; i<n; i++) scanf("%d", &s[i]);
47 for(int i=0; i<m; i++) scanf("%d", &t[i]);
48 getnxt(t, m);
49 int ans = KMP(s, t, n, m);
50 printf("%d\n", ans == -1 ? -1 : ans+1);
51 }
52 return 0;
53}