kmp算法

int* kmp_next(char p[])

{

  int len = strlen(p);

  int *next = new int[len];

  memset(next, 0, sizeof(int) * len);

  next[0] = -1;

  next[1] = 0;

  for (int j = 2; j < len; j++)

  {

    int k = next[j - 1];

    if(p[k] == p[j - 1])

    {

      next[j] = next[j - 1] + 1;

    }

    else

      int i = next[k];

      while (i > -1 && p[i] != p[j - 1])

      {

        i = next[i];

      }

      next[j] = i + 1;

  }

  return next;

}

bool kmp(char t[], char p[], int &pos)

  int i = 0;

  int j = 0;

  int len1 = strlen(t);

  int len2 = strlen(p);

  int *next = kmp_next(p);

  while(i < len1)

    if (t[i] == p[j])

      i++;

      j++;

      if (j == len2)

        pos = i - len2;

        return true;

      j = next[j];

      if (j < 0)

        i++;

        j = 0;

  delete []next;

  pos = -1;

  return false;