Zhao70's Blog

KMP算法

发表于 | 分类于

简介

想KMP这个算法的时间， 前前后后加起来能有48个小时吧。 学这种算法还是画画图实在啊， 空想是没有用的~

kmpSearch

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int kmpSearch(const string &s, const string &p)
{
    int i = 0;
    int j = 0;
    int sLen = s.length();
    int pLen = p.length();
    while(i < sLen && j < pLen)
    {
        if(j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j == pLen)
        return i - j;
    else
        return -1;
}

讲解

对于kmpSearch这个函数来讲， 思路是不难理解的。 不过此 i，j 的变化和边界是需要特别注意的。

  1. 可以将 i, j 理解为指针， 所谓的-1即为空指针。
  2. 当 j 的值为 -1 时， 说明 p 中已经没有可以匹配的前缀了。 所以 i, j分别自增 1。 i 指向下一个 s 中的字符。 j 指向 p[0].

  3. 跳出while循环的可能性:

    1. i 遍历 s 中所有元素
    2. j 遍历 p 中所有元素

    只有第 2 种情况说明字符串完全匹配。 返回值 i 中找到的字符串结尾 减去 字符串 p 的长度(即 j)。

getNextVal

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getNextVal(const string &p)
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    int pLen = p.length();
    while(j < pLen - 1)
    {
        if(k == -1 || p[k] == p[j])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

讲解

next数组可是kmp算法的精华啊， 最开始看next数组生成过程的时候，有一种很玄学的感觉。。。

next数组的含义

代表当前字符之前的字符串中，有多大长度的相同前缀后缀。
例如 如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

  1. k, j分别是指向相同前后缀最后一个字符的指针。
  2. 当 p[k] == p[j] 时，k，j 自增一。 因为 k 为指向前缀的指针， 即为前缀的长度， k 的大小即最长相同前后缀的长度
  3. 因为 j 的取值范围为[0, pLen - 1] 但 next 数组的含义为 “代表当前字符之前的字符串中，有多大长度的相同前缀后缀”, 所以判断到 p[plen - 2]的字符 即可得到 next[pLen - 1]的值。
  4. 题目中的 i, j 为先判断后更新 next 的值， 保证了 3 的成立。
  5. 当p[k] != p[j]时, 便寻找更小的后缀 k = next[k]
    第五条我想了整整一下午，

    举个例子
    前缀1 和 后缀1 相同
    前缀1 包括相同的 前缀a 和 后缀b
    后缀2 包括相同的 前缀c 和 后缀d
    因为 1 == 2
    所以 a == b == c == d
    所以可以放弃 1 + p[k] 与 2 + p[j]
    来更新 a + p[k] (k = next[k]) 和 d + p[j] (j值未变)

next数组优化

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void getNextVal(const string &p)
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    int pLen = p.length();
    while(j < pLen - 1)
    {
        if(k == -1 || p[k] == p[j])
        {
            j++;
            k++;
            if(p[k] != p[j])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

讲解

当p[j] == p[next[j]]时， 匹配是无效的。 所以不能允许p[j] == p[next[j]]。如果出现了p[j] == p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[next[j]]。

相关链接

关于 KMP 算法，july的博客中的关于KMP的置顶文章绝对是我目前为止见过的最好的文章了， 通俗易懂， 深入浅出。 比其他文章不知道高到哪里去了。

从头到尾彻底理解KMP（2014年8月22日版）