KMP算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
  char *pStr;
  int length;
} String;

int KMP(String *T, String *P, int next[]) {
  int i = 0, j = 0, m = T->length, n = P->length;
  while (i <= m - n) {
    while (j == -1 || (j < n && T->pStr[i] == P->pStr[j])) {
      i++;
      j++;
    }

    if (j == n) {
      return (i - n);
    }
    j = next[j];
  }
  return -1;
}

void BuildNext(String *P, int next[]) {
  int j = 0, k = -1, n = P->length;
  next[0] = -1;
  while (j < n) {
    if (k == -1 || P->pStr[j] == P->pStr[k]) {
      next[j + 1] = k + 1;
      j++;
      k++;
    } else {
      k = next[k];
    }
  }
}

void BuildNextval(String *P, int nextval[]) {
  int j = 0, k = -1, n = P->length;
  nextval[0] = -1;
  while (j < n) {
    if (k == -1 || P->pStr[j] == P->pStr[k]) {
      j++;
      k++;
      if(P->pStr[j] != P->pStr[k]){
        nextval[j] = k;
      }
      else{
        nextval[j] = nextval[k];
      }
    } else {
      k = nextval[k];
    }
  }
}