数字kmp.
pure water.
#include <cstdio> using namespace std; const int MAXN = 1000005; const int MAXM = 10005; int n,m,a[MAXN],b[MAXM],k; int next[MAXM]; void prekmp() { next[0] = -1; int j = -1; for(int i=1;i<m;i++) { while(j!=-1 && b[j+1]!=b[i]) j = next[j]; if(b[j+1]==b[i]) j++; next[i] = j; } } int kmp() { int j = -1; for(int i=0;i<n;i++) { while(j!=-1 && b[j+1]!=a[i]) j = next[j]; if(b[j+1]==a[i]) j++; if(j==m-1) return i-j+1; } return -1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<m;i++) scanf("%d",b+i); prekmp(); printf("%d\n",kmp()); } }