KMP算法

KMP算法,第1张

算法

记文本串为t,模式串为p,如下图:

假设已经匹配到了一部分,但是在箭头所指处,两字符不匹配。


对于朴素匹配算法,现在需要把串p往后移一步,再从头开始对字符一个个比较。


由于已匹配部分完全相同,所以两者有相同的A部分与B部分,那么如果模式串p中有A = B,我们实际上就可以把p移到p'的位置,再从箭头位置开始比较。


也就是说,如果模式串p在 i 位置发生了不匹配,我们知道它的[0 ~ i - 1]部分的相同的前缀A和后缀B,那么就可以对模式串p进行移动。


注:这里若有多组相同的A和B,应该取最长的那一组。


预处理

预处理就是在开始匹配前,把模式串中每个位置 i 对应的的最长的A = B的长度求出,也就是next数组。


这里的预处理用到了动态规划的思想:

假设现在已经计算了前 i 个next,计算i + 1时,有两种情况:

情况1

这里A和B为 next[i] 部分的最长的相同前后缀,如果i + 1位置的字符和A后面的一个字符相同,那么就有next[i + 1] = next[i] + 1。


情况2

如果不同:

 那么next[i + 1]一定比next[i]小(可反证),设i + 1的相同前后缀 = C部分 + O:

注意到A = B,所以C是B的后缀,所以也是A的后缀,那么C也就是A的相同前后缀, 只要比较C后面的字符是否是O即可,如果不同,则继续递归的寻找下去。


代码如下:

/*
 * next记录的是长度
 */
void GetNext(const string& p, vector& next) {
  next[0] = 0;
  int k = 0;
  for (int i = 1; i < p.size(); ++i) {
    while (k > 0 && p[k] != p[i]) {
      k = next[k - 1];
    }
    if (p[k] == p[i]) {
      ++k;
    }
    next[i] = k;
  }
}

搜索
bool KMPSearch(const string& s, const string& p) {
  vector next(p.size());
  GetNext(p, next);
  int i = 0, j = 0;
  while (i != s.size() && j != p.size()) {
    if (s[i] == p[j]) {
      ++i;
      ++j;
    } else {
      if (j == 0) {
        ++i;
      } else {
        /* j位置不匹配,根据next[j - 1]进行移动 */
        j = next[j - 1];
      }
    }
  }
  return j == p.size();
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562906.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存