kuangbin专题16A(kmp模板)

题目链接: https://vjudge.net/contest/70325#problem/A

题意: 有两个数组 a, b, 输出 b 数组在 a 数组中的第一个匹配位置, 不能匹配则输出 -1.

思路: kmp模板

代码:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 const int MAXN = 1e6 + 10;
 7 int a[MAXN], b[MAXN], nex[MAXN];
 8 int n, m;
 9 
10 void get_next(int *b){
11     nex[0] = 0;
12     for(int i = 1; i < m; i++){
13         int j = nex[i];
14         while(j && b[j] != b[i]){
15             j = nex[j];
16         }
17         nex[i + 1] = j + (b[i] == b[j]);
18     }
19 }
20 
21 int kmp(int *a, int *b){
22     get_next(b);
23     for(int i = 0, j = 0; i < n; i++){
24         while(j && a[i] != b[j]){
25             j = nex[j];
26         }
27         if(a[i] == b[j]) j++;
28         if(j == m) return i - m + 2;
29     }
30     return -1;
31 }
32 
33 int main(void){
34     int t;
35     scanf("%d", &t);
36     while(t--){
37         memset(nex, 0, sizeof(nex));
38         scanf("%d%d", &n, &m);
39         for(int i = 0; i < n; i++){
40             scanf("%d", &a[i]);
41         }
42         for(int i = 0; i < m; i++){
43             scanf("%d", &b[i]);
44         }
45         int sol = kmp(a, b);
46         printf("%d
", sol);
47     }
48     return 0;
49 }

View Code