KMP 算法

KMP算法经常忘记它的内涵,在这里记录一下希望能记住

KMP算法全称是 Knuth-Morris-Pratt 算法 KMP算法是其简称，用于处理字符串的模式比较，B串是否是A串的子串。如果采用暴力方法，时间复杂度是 O(m*n)。KMP算法让子串在发现不匹配时，尽可能地向后移动。需要子串的部分匹配表，即next数组，next数据的求解方法如下。next数组的意义是让算法尽可能地绕过无效的字符序列

void getNext(char *p, int* next) {
  next[0] = -1;
  int i = 0, j = -1;
  while (i < strlen(p)) {
    if (j == -1 || p[i] == p[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
}

int kmp(string s_primary, string s_mode, int pos, int *next) {
  int i = pos;
  int j = 1;

  int len_p = s_primary.size();
  int len_m = s_mode.size();

  while (i < len_p && j < len_m) {
    if (j == 0 || s_primary[i] == s_mode[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }

  if (j >= len_m) {
    return i = len_m;
  } else {
    return 0;
  }
}

kmp 算法的时间复杂度是 O(n+m)，就是在匹配失败时，总能让子串回退到某个位置，让text不用回退。

Written on October 18, 2019