KMP算法

编程爱好者联盟 2016-12-12

KMP算法是字符串模式匹配当中最经典的算法,原来大二学数据结构的有讲,但是当时只是记住了原理,但不知道代码实现,今天终于是完成了KMP的代码实现。原理KMP的原理其实很简单,给定一个字符串和一个模式串,然后找模式串在给定字符串中的位置。将两个字符串转换为字符数组,然后从两个数组的开始位置"i","j"开始匹配,如果相同,执行"i++","j++"接着比较下一位;如果不相同,就转到模式串对应next数组的对应位置"next[j]"然后从该位置开始继续与给定字符串的当前位置"i"进行比较,换句话说就是将模式串提前了"j-next[j]"位继续比较,不至于每次出现不匹配就又重新回到开始位置进行匹配,充分利用了已匹配过的位置。

代码KMP算法的关键是得到模式串的next数组:

public static int[] next(char[] p) {
  int len = p.length;
  int[] next = new int[len];
  next[0] = 0;
  next[1] = 0; //首先给next[0]和next[1]赋值,这两个数字是固定的
  for(int i = 2; i < len; i++) {
    int k = next[i - 1]; //用一个整型数字进行遍历
    while(k >= 0) {
      if(p[i - 1] == p[k]) {
        next[i] = k + 1; //当匹配到字符时就能得到当前位置的next值,然后结束循环
        break;
      }
      k--;
    }
  }
  return next;
}

得到next数组之后就可以进行KMP匹配:

public int kmpSearch(char[] s, char[] p) {
  int i = 0, j = 0; //从0开始
  int slen = s.length, plen = p.length;
  int[] next = next(p);
  while(i < slen && j < plen) {
    if(s[i] == p[j]) { //挨个进行匹配
      i++;
      j++;
    } else {
      j = next[j]; //如果不相等,返回next[j]位置继续向后匹配,不用和前面的进行比较
    }
  }
  if(j == plen) //如果匹配到最后,说明匹配成功,返回匹配成功的开始位置
    return i - j;
  return -1; //否则就是匹配失败,返回-1
}

KMP算法还有一个进阶的next算法,求nextval数组:

public int[] nextVal(char[] p) {
  int len = p.length;
  int[] nextval = new int[len];
  nextval[0] = -1;
  int i=-1, j = 0;
  while(j < len - 1) {
  if(i == -1 || p[j] == p[i]) {
    ++i;
    ++j;
    if(p[j] != p[i])
      nextval[j] = i;
    else
      nextval[j] = nextval[i];
  }else 
      i = nextval[i];
  }
  return nextval;
}

相关推荐