KMP算法一知半解

作者: 烟影很美 | 来源:发表于2021-12-03 14:48 被阅读0次

KMP 专题整理
对KMP算法的一些理解
KMP算法一知半解
KMP算法文章合集
串的模式匹配算法
问答|KMP算法学习笔记
KMP算法——寻找子串位置
字符串匹配 - KMP算法
KMP算法及优化
KMP算法(字符串匹配问题)

KMP算法是用来匹配字符串的，比如在字符串** haystack:ABCACEABCABDA中查询是否存在子串 needleABCAB，这种问题可以暴力破解，即：将 haystack中所有长度与needle相等的字串与needle**比较。

KMP与暴力破解的区别在于：

暴力破解是** haystack的子串ABCAC(_ABCACEABCABDA)与needle**ABCAB比较后，由于不匹配，接下来会用BCACE(A_BCACEABCABDA)与ABCAB比较。
KMP相对“智能”一些，若ABCAC(_ABCACEABCABDA)与ABCAB比较不匹配后，会选ACEAB(ABC_ACEABCABDA)与needle比较，至少，他们有相同的开头。那么，如何才能正确选择到相同开头的字串是KMP的关键。

在KMP中通过部分匹配表来实现相对智能选择合适的开头。部分匹配表是对字符串needle的一种“描述”，取字符串“前缀”和后缀的最大共有长度，其规则如下：

－　"A"的前缀和后缀都为空集，共有元素的长度为0；
－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　"ABCA"的前缀为[A, AB, ABC]，后缀为[BCA, CA, A]，共有元素的长度为，共有元素为“A”，长度为1；
－　"ABCAB"的前缀为[A, AB, ABC, ABCA]，后缀为[BCAB, CAB, AB, A]，共有元素为"AB"，长度为2；

故needle的部分匹配表为[0,0,0,1,2]。ABCAC(_ABCACEABCABDA)与needleABCAB比较后，下一次比较开始的位置为本次匹配开始的位置再向右偏移x位，其中x的值是ABCAC与ABCAB的最大匹配长度4(ABCA)减去最后一个匹配的字母A在部分匹配表中`所对应的值。即：

移动位数 = 已匹配的字符数 - 已匹配的最后一个字符对应匹配值

其中的原理大概描述是：

ABCAC与ABCAB比较，其中匹配的部分是ABCA。由于最终还是不匹配，出于效率考虑，下次比较开始的位置需要尽可能靠后，那不如向右数4位吧(ABCA的长度)，但这个万一ABCA中某部分也可以作为下次比较的开头呢？通过“观察”发现ABCA末尾的只有A可以作为下一次的开始(如果是ABAB，那么就是末尾的AB可以作为下次比较的开始)，那就向右数4-1位吧。

上述过程的写成伪代码：

// 部分匹配表
int pi[needle长度]
// pi的计算
...
// 遍历
int i = 0, j = 0;
while (i < n) {
  if (haystack[i] == needle[j]) {
    j++;
    i++;
  } else {
    if (j > 0) {
      i = i + j - pi[j-1];
    }
    j = 0;
  }
  if (j == m) {
    return i - j;
  }
}

然而这并不是最好的方案，当haystack[i] != needle[j]的时候，改变i和j不如单独改变j，即ABCAC(_ABCACEABCABDA)与ABCAB比较不匹配后，会选ACEAB(ABC_ACEABCABDA)与needle比较，，也可以理解为haystack[4] != needle[4]时，i==4不变，j=1，这样i==3就不用再比较一次了，而匹配表中的数据恰好可以直接给赋值给j。如下图：

伪代码：

// 部分匹配表
int pi[needle长度]
// pi的计算
...
// 遍历
int i = 0, j = 0;
while (i < n) {
  if (haystack[i] == needle[j]) {
    j++;
    i++;
  } else {
    if (j == 0) {
      i++;
    } else {
      j = pi[j-1];
    }
  }
  if (j == m) {
    return i - j;
  }
}

好了，目前为止，至少KMP的原理是知道了，下面看看KMP的标准代码

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0) {
        return 0;
    }
    // 部分匹配表 pi
    int pi[m];
    pi[0] = 0;
    // pi的计算
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        pi[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

？？？！！！
什么鬼？pi到底是怎么计算出来的？

有以下三个思考点。

计算过程可以看成needle与needle’（needle == needle‘）字母依次比较比较，只不过最开始是needle[i]与needle’[j], i == 1, j==0 且i > j永远成立;
动态规划：pi[0]==0且pi[i+1] <= pi[i]+1。
有限状态自动机：pi中所保存的，是对应状态遇到不符合期望的条件将要切换到的状态。状态j，0 <= j <= needle的长度，当j==needle的长度，检索成功。