HDU 1711 Number Sequence(KMP)

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
int s[maxn], p[10005];
int Next[10005];
int T, n, m;

void init(){
    int j = 0, k = -1;
    memset(Next, -1, sizeof(Next));
    while(j < m){
        if( k == -1 || p[j] == p[k]){
            k ++;
            j ++;
            Next[j] = k;
        }
        else k = Next[k];
    }
}

int kmp(){
    int i = 0, j = 0;
    while(j < n){
        if(i == -1 || p[i] == s[j]){
            i ++;
            j ++;
        }
        else{
            i = Next[i];
        }
        if(i == m){
            return j - m;
        }
    }
    return -1;
}

int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%d", &s[i]);
        for(int i=0;i<m;i++)scanf("%d", &p[i]);
        init();
        int ans = kmp();
        printf("%d\n", ans == -1 ? ans : ans + 1);
    }
    return 0;
}