题意：
给出两个数字序列 : a[1], a[2], ...... , a[N], 和 b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). 你的任务是找到一个数字K满足： a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. 如果有多个K满足题意，请你输出最小的那个K。
输入
第一行是一个数字T代表有T组测试数据. 每组测试数据有三行. 第一行是两个数字 N and M (1 <= M <= 10000, 1 <= N <= 1000000). 第二行包括N个整数代表a[1], a[2], ...... , a[N]. 第三行包括M个整数代表b[1], b[2], ...... , b[M]. 所有数字的范围在[-1000000, 1000000]之间。
输出
对于每组测试数据, 你应该输出一行答案。代表K, 如果没有符合题意的K,那么输出-1。
这是一道模板题，希望做题的时候可以裸敲不要看模板，这样可以更深度的理解什么是KMP算法。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN=1e6+5; int N, M; int a[maxN], b[maxN]; void cal_next(int *next) { next[1]=0; int k = 0; for(int i=2; i<=M; i++) { while(k>0 && b[k+1]!=b[i]) { k=next[k]; } if(b[k+1] == b[i]) k++; next[i]=k; } } int KMP() { int *next = new int[M+1]; cal_next(next); int k = 0; for(int i=1; i<=N; i++) { while(k>0 && b[k+1]!=a[i]) { k=next[k]; } if(b[k+1] == a[i]) k++; if(k == M) return i-M+1; } return -1; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &N, &M); for(int i=1; i<=N; i++) scanf("%d", &a[i]); for(int i=1; i<=M; i++) scanf("%d", &b[i]); printf("%d\n", KMP()); } return 0; }
