KMP算法理解

KMP的由来

在KMP算法之前,对文本进行匹配时使用的是朴素模式匹配算法,也就是最简单匹配算法.
当然运行效率也是让人深恶痛绝,举个例子:

现有长度为n的模式串00001,和长度为m的文本串0000000000000000000000000000000001.
按照朴素匹配算法最终时间复杂度为o{(m-n+1)*n}

这种有多个0和1重复字符的字符串,匹配模式却仍需要挨个遍历,这是十分糟糕的,所以最终KMP算法诞生了.

KMP和朴素算法的核心差别

朴素算法在匹配时,子串和对比的目标串都会不断的进行回溯对比,而KMP会先计算出子串的匹配数组,在进行匹配时目标串并不会进行回溯,且子串回溯时会根据计算出的重复数组省略很多不必要的回溯.
下面就用例子进行讲解.

KMP的回溯原理

引用阮一峰:字符串匹配的KMP算法

以下图两字符串匹配为例:

未编译

KMP核心是找出要匹配的子串的匹配值数组,如下图给出的子串和匹配值.

未编译

"子串匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,
"A"的前缀和后缀都为空集,共有元素的长度为0;
"AB"的前缀为[A],后缀为[B],共有元素的长度为0;
"ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
"ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
"ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

跳过前面一端不匹配的,我们直接来到匹配串生效的位置

已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4,所以将搜索词向后移动4位。

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

因为空格与A不匹配,继续后移一位。

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

这么一看KMP是不是比朴素算法匹配次数少了很多?例子中也看出了KMP核心在于匹配数组,那如何通过代码求出匹配数组呢?

KMP核心匹配串数组

下面是Java的伪代码


    public int[] get_next(char[] str) {
        int i = 1;
        int j = 0;
        int[] next = new int[str.length];
        next[0] = 0;
        while (i < str.length) {
            if (str[i]==(str[j])) { // 匹配记录下当前匹配的位置
                ++j;
                next[i] = j;  // 为了配合例子更便于理解,所以在++i之前便给匹配数组进行了赋值
                ++i;
            } else if (j == 0) {  // 完全不匹配,跳至下一个字符
                next[i] = j;  // 同上理由
                ++j;
                ++i;
            } else {
                j = next[j - 1];  // 回溯至合适的位置
            }
        }
        return next;
    }

这段代码中j = next[j - 1];是很多人懵逼的地方,当然常规模式是j = next[j];.我这里配合例子进行了改写.
为什么不是递减回溯,而是直接跳至数组中的匹配值,尽管从结果中可以看出这样确实是高效的方式,但是为什么正好就是最合适呢?知其然不知其所以然.

下面按照上面思路来实现KMP算法就能知其所以然了.

KMP算法具体实现

    // 求字符串t,在字符串s中的pos位之后首次出现的位置
    public int index_KMP(char[] s, char[] t, int pos) {
        int i = pos;
        int j = 0;
        int[] next = get_next(t);
        while (i < s.length && j < t.length) {
            if (s[i] == t[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                // j的回溯位置可以根据上面例子中的公式来套.
                // 移动位数 = 已匹配的字符数 - 对应的部分匹配值;
                // 已匹配的字符数为: j;
                // 对应部分匹配值为: next[j - 1];
                // 移动位数为: j - (next[j - 1]);
                // 新的索引 = 旧索引 - 移动位数;
                // j = j - (j - (next[j - 1]));
                j = next[j - 1];
            }
        }
        if (j == t.length) {
            return i - t.length;
        }
        return 0;
    }

从这里就可以看出为什么回溯的位置是j = next[j - 1],在于常规的对应一下,常规的kmp算法数组中当前位对应的是前一位的重复值,并不是本身的重复值.
在上述公式中我们需要找到前一位的对应值,来进行位移操作,而常规KMP中前一位重复值就是next[j].
所以最终的回缩过程就是 j = next[j];

便于理解,在求自身匹配数组时,也可以将不断变换的尾串看做成子串,这样就是子串和目标串进行匹配,就可以套用上面的公式得出j = next[j],只不过尾串一直在变化而已.

在改进KMP算法时,需先将算法恢复到正常模式(想了半天不知道在改进模式的情况下如何继续推导了...)
常规的KMP匹配数组获取代码如下:

    // 由于数组的角标是从0开始的,所以的出来的结果和书上所说的统统小一.
    public int[] get_next(char[] str) {
        int i = 0;
        int j = -1;
        int[] nextval = new int[str.length];
        nextval[0] = -1;
        while (i < str.length - 1) {
            if (j == -1 || str[i] == (str[j])) {   // 匹配记录下当前匹配的位置
                ++j;
                ++i;
                nextval[i] = j;
            } else {
                j = nextval[j];  // 回溯至合适的位置
            }
        }
        return nextval;
    }

常规模式KMP匹配代码如下:

    public int index_KMP(char[] s, char[] t, int pos) {
        int i = pos;
        int j = 0;
        int[] next = get_next(t);
        while (i < s.length && j < t.length) {
            if (j == 0 || s[i] == t[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == t.length) {
            return i - t.length;
        }
        return 0;
    }

KMP算法的改进

引自July:从头到尾彻底理解KMP(2014年8月22日版)
用前面的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它跟下图中的文本串去匹配的时候,发现b跟c失配,于是模式串右移j - next[j] = 3 - 1 =2位。

P表子串(abab),s表目标串(abacabababc)
右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知p[3] = b,与s[3] = c失配,而右移两位之后,让p[next[3]] = p[1] = b 再跟s[3]匹配时,必然失配。问题出在哪呢?

问题出在不该出现p[j] = p[next[j]]。为什么呢?理由是:当p[j] != s[i] 时,下次匹配必然是p[next[j]] 跟s[i]匹配,如果p[j] = p[next[j]],必然导致后一步匹配失败(因为p[j]已经跟s[i]失配,然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配,很显然,必然失配),所以不能允许p[j] = p[next[j]]。如果出现了p[j] = p[next[j] ]咋办呢?如果出现了,则需要再次递归,即令next[j] = next[next[j]]。

    public int[] get_nextval(char[] str) {
        int i = 0;
        int j = -1;
        int[] nextval = new int[str.length];
        nextval[0] = -1;
        while (i < str.length - 1) {
            if (j == -1 || str[i] == (str[j])) {   // 匹配记录下当前匹配的位置;
                ++j;
                ++i;
                nextval[i] = j;
                if (str[i] != str[j]) { // 当前字符与前缀字符不同;
                    nextval[i] = j;  // 当前的j赋值给nextval[i];
                } else {
                    nextval[i] = nextval[j]; // 与前缀字符相同,那么将前缀字符的nextval值付给在i位的值.
                }
            } else {
                j = nextval[j];  // 回溯至合适的位置
            }
        }
        return nextval;
    }

本文到此结束.
前面KMP推导算是个人理解,后面的改进照搬July的,因为实在说的很清楚了,没有能补充的,若还是有点蒙圈,可以看July原文,或许更容易理解.

参考博客

阮一峰:字符串匹配的KMP算法
July:从头到尾彻底理解KMP(2014年8月22日版)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容

  • 文章大纲:1.KMP算法概念2.KMP算法中最核心的next[] 数组是如何生成的3.使用KMP算法 匹配字符串 ...
    柠檬乌冬面阅读 807评论 0 3
  • 数据结构与算法--KMP算法查找子字符串 部分内容和图片来自这三篇文章: 这篇文章、这篇文章、还有这篇他们写得非常...
    sunhaiyu阅读 1,723评论 1 21
  • 数据结构 第8讲 KMP算法 讲这个算法之前,我们首先了解几个概念: 串:又称字符串,是由零个或多个字符组成的有限...
    rainchxy阅读 1,268评论 0 3
  • 引言 字符串匹配一直是计算机科学领域研究和应用的热门领域,算法的改进研究一直是一个十分困难的课题。作为字符串匹配中...
    潮汐行者阅读 1,624评论 2 6
  • 最初想写下这篇观后感时的心情和此刻我下笔的心情完全不一样。 把第七季养肥后,我开始关注这部剧的花边,一些剧情,例如...
    慕倾所向阅读 532评论 0 3