思路：模板题，用整数数组把主串模式串存起来。
#include <cstdio> using namespace std; const int N = 1e6 + 5; int s[N], p[N]; int sl, pl, next[N]; void get_next(){ int i = 0,j = -1; next[0] = -1; while(i < pl) { if(j == -1 || p[i] == p[j]) next[++i] = ++j; else j = next[j]; } } int kmp(){ get_next(); int i = 0, j = 0; while(i < pl && j < sl){ if(i == -1 || p[i] == s[j]){ ++i; ++j; } else{ i = next[i]; } } if(i == pl){ return j - i + 1; } return -1; } int main() { int n; scanf("%d", &n); while(n--){ scanf("%d %d", &sl, &pl); for(int i = 0; i < sl; ++i){ scanf("%d", &s[i]); } for(int i = 0; i < pl; ++i){ scanf("%d", &p[i]); } printf("%d\n", kmp()); } return 0; }