1  #include <cstdio> 2  using namespace std; 3  4  const int MAXN = 1e6 + 10; 5  int nex[MAXN]; 6  int s[MAXN], t[MAXN]; 7  8  void get_nex(int lm)    { 9      int i = 0, j = -1;   nex[0] = -1;10      while (i < lm)  {11          if (j == -1 || t[j] == t[i]) {12              i++;    j++;    nex[i] = j;13          }14          else    j = nex[j];15      }16  }17 18  int KMP(int ln, int lm)   {19      get_nex (lm);20      int i = 0, j = 0;21      while (i < ln)  {22          while (j != -1 && s[i] != t[j]) j = nex[j];23          i++;    j++;24          if (j == lm) return (i - j + 1);25      }26      return -1;27  }28 29  int main()    {30      int T;31     scanf ("%d", &T);32      while (T--)   {33          int ln, lm; scanf ("%d%d", &ln, &lm);34          for (int i=0; i<ln; ++i)   scanf ("%d", &s[i]);35          for (int i=0; i<lm; ++i)   scanf ("%d", &t[i]);36          printf ("%d\n", KMP (ln, lm));37      }38 39      return 0;40  }