KMP算法模板 求子串和模板串首先匹配的位置

 #include <cstdio>
 using namespace std;

 const int MAXN = 1e6 + 10;
 int nex[MAXN];
 int s[MAXN], t[MAXN];

 void get_nex(int lm)    {
     int i = 0, j = -1;   nex[0] = -1;
     while (i < lm)  {
         if (j == -1 || t[j] == t[i]) {
             i++;    j++;    nex[i] = j;
         }
         else    j = nex[j];
     }
 }

 int KMP(int ln, int lm)   {
     get_nex (lm);
     int i = 0, j = 0;
     while (i < ln)  {
         while (j != -1 && s[i] != t[j]) j = nex[j];
         i++;    j++;
         if (j == lm) return (i - j + 1);
     }
     return -1;
 }

 int main()    {
     int T;
    scanf ("%d", &T);
     while (T--)   {
         int ln, lm; scanf ("%d%d", &ln, &lm);
         for (int i=0; i<ln; ++i)   scanf ("%d", &s[i]);
         for (int i=0; i<lm; ++i)   scanf ("%d", &t[i]);
         printf ("%d
", KMP (ln, lm));
     }

     return 0;
 }