模板...嗯
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #pragma warning ( disable : 4996 ) 5 using namespace std; 6 7 const int inf = 0x3f3f3f3f; 8 const int maxn = 1e4+5; 9 const int vspot = 1e6+5; 10 11 int net[maxn]; 12 int num[maxn], test[vspot]; 13 int N, M, ans; 14 15 void getnext() 16 { 17 memset( net, 0, sizeof(net) ); 18 ans = 0; 19 int len = M; 20 21 int k = -1, j = 0; 22 net[j] = -1; 23 24 while ( j < len-1 ) 25 { 26 if ( k==-1 || num[j]==num[k] ) 27 { 28 k++; 29 j++; 30 net[j] = k; 31 } 32 else 33 k = net[k]; 34 } 35 } 36 37 void solve() 38 { 39 int i = 0, j = 0; 40 while ( i < N && j < M ) 41 { 42 if( j == -1 || test[i] == num[j] ) 43 { i++; j++; } 44 else 45 j = net[j]; 46 } 47 if( j == M ) 48 ans = i-j+1; 49 else 50 ans = -1; 51 } 52 53 int main() 54 { 55 int all; 56 cin >> all; 57 while (all--) 58 { 59 cin >> N >> M; 60 for( int i = 0; i < N; i++ ) 61 scanf( "%d", &test[i] ); 62 for( int i = 0; i < M; i++ ) 63 scanf( "%d", &num[i] ); 64 65 getnext(); 66 solve(); 67 printf( "%d\n", ans ); 68 } 69 return 0; 70 }