kuangbin专题16A(kmp模板)

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

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

思路: kmp模板

代码:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 const int MAXN = 1e6 + ;

 int a[MAXN], b[MAXN], nex[MAXN];

 int n, m;

 void get_next(int *b){

     nex[] = ;

     for(int i = ; i < m; i++){

         int j = nex[i];

         while(j && b[j] != b[i]){

             j = nex[j];

         }

         nex[i + ] = j + (b[i] == b[j]);

     }

 }

 int kmp(int *a, int *b){

     get_next(b);

     for(int i = , j = ; i < n; i++){

         while(j && a[i] != b[j]){

             j = nex[j];

         }

         if(a[i] == b[j]) j++;

         if(j == m) return i - m + ;

     }

     return -;

 }

 int main(void){

     int t;

     scanf("%d", &t);

     while(t--){

         memset(nex, , sizeof(nex));

         scanf("%d%d", &n, &m);

         for(int i = ; i < n; i++){

             scanf("%d", &a[i]);

         }

         for(int i = ; i < m; i++){

             scanf("%d", &b[i]);

         }

         int sol = kmp(a, b);

         printf("%d\n", sol);

     }

     return ;

 }