初学 Kmp ，推荐 严蔚敏教授 的数据结构视频11和12，讲解的很清楚。
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 using namespace std; 5 int N, M, next[10005], S[1000005], T[10005]; 6 7 void getNext() { 8 int j = 0, k = -1; 9 next[0] = -1; 10 while (j < M) { 11 if ((-1 == k) || (T[j] == T[k])) { 12 ++j; ++k; 13 if (T[j] != T[k]) next[j] = k; 14 else next[j] = next[k]; 15 }else k = next[k]; 16 } 17 } 18 19 int Solve() { 20 int i = 0, j = 0; 21 while ((i < N) && (j < M)) { 22 if ((-1 == j) || (S[i] == T[j])) { 23 ++i; ++j; 24 }else j = next[j]; 25 } 26 if (M == j) return (i - M + 1); 27 else return -1; 28 } 29 30 int main() { 31 int Case; 32 scanf("%d", &Case); 33 while (Case--) { 34 scanf("%d %d", &N, &M); 35 for (int i = 0; i < N; ++i) { 36 scanf("%d", &S[i]); 37 } 38 for (int j = 0; j < M; ++j) { 39 scanf("%d", &T[j]); 40 } 41 getNext(); 42 printf("%d ", Solve()); 43 } 44 return 0; 45 }