模板...嗯

1 #include 
      
        2 #include 
       
         3 #include 
        
          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         else33             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         else45             j = net[j];46     }47     if( j == M )48         ans = i-j+1;49     else50         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 }