smril's blog
0%

KMP算法详解

发表于 分类于

KMP算法详解

KMP算法比朴素匹配好在哪呢？i不用回溯，j通常不用回溯到头，可以减少回溯到成本。

KMP算法原理

如一个串：abaabcac
这个为模式串，用这个串去匹配长字符串，随便写一个：abaccaabcabaababaabcacba
用朴素的模式匹配便是一次匹配不上往前移一个，再次匹配，这样暴力匹配的效率比较低，而且两个指针都需要回溯到最开始，比较消耗资源，KMP便是一个i指针（指被匹配串的指针）不用回溯，j指针通常不用回溯到头的算法。

步骤如下：

首先先正常匹配，现在前三位匹配上了
a b a c c a a b c …
a b a a a b c a c
第四位没匹配上，那么我们要回溯，首先i指针不用动，上面的串看到哪里就是哪里，我们只看下面的串，因为上面的串i前面的内容已经和下面的串匹配上了，相当于上面的串的信息记录到了下面的串（模式串）里，如上面是ab，下面也是ab，则我们只用知道下面的串就知道上面i前面的一定是ab。
j指针要回溯，回溯到哪里呢？
这时我们只看模式串，因为上面的信息也在模式串里，这时我们想要尽可能的往后推，因为这样算法会更快，那么我们能推多少位，就取决于主串没匹配上的字符前面的字符和模式串开头字符到底有多少位重合，如主串上没匹配的是c，前面是aba，从后往前看的子串有a, ba, 模式串匹配上的也是aba, 所以看模式串结尾和看主串结尾是一样的，我们只用看模式串就好了，接下来看模式串开头，子串为a, ab，我们发现主串的末尾和模式串的开头有一个a相同，所以我们就知道了有一个a相同，所以只能推两位，变为：
a b a c c a a b c …
____a b a a a b c a c
试想如果一个相同的都没有，说明我们就算一个一个推，它也根本匹配不上，因为模式串未匹配上字符之前串的末尾（主串未匹配上字符之前串的末尾）根本就与开头不相同，那么意味这个i之前的串已经没有匹配上这个模式串的可能，这所以我们就可以一股脑的全推过去，效率大大增加。

既然现在一个模式串就可以决定推几步（比如上面，有一个相同的a就知道模式串应该推到开头a的下一位），我们就用一个next数组算出模式串的每一个字符如果没匹配上，那么它应该推几步。

next数组计算

next数组记录了当前字符没匹配上的话，模式串应该回退到哪个位置，比如对比上面的例子，next[4]表示了现在模式串的第四位a没匹配上，那么next[4]应该等于1，即下一次模式串用1位置的b来匹配主串的i位置，为什么等于1呢？因为模式串的第1位为b(a第0位)，这个1的意思就是模式串没匹配上的字符之前的字符和模式串开始往后的字符相同的个数，现在比如有这么个串：
a b a c a b a d
那么d的next值就应该是c的下标，即为3，因为c之前的串为aba,d之前的串也为aba（当然a也可以，但是我们要找最长的，否则会推的太放肆漏掉正确结果），这就意味着下一次可以直接用c去匹配d没有匹配上的字符，因为c和d前面都是一样的。

那么abaaabcac这个串的next值就应该为：

a b a a a b c a c
0 0 0 1 1 1 2 0 1

这个next是不对的，因为第一位的下标是0，意味着第一位匹配不上的话还是回到第一位，这样的话就永远循环了，为什么呢？因为如果有这样的循环，说明没匹配上的字符前面根本没有相同的，所以我们要一股脑的全部推出去，即i++，这意味着主串终于变了。所以我们把它改写为这样：

_a b a a a b c a c
-1 0 0 1 1 1 2 0 1

这样next数组就计算完了，如果第一个a的下标为1的话就全部加一：011222312

代码解读：

网上流传有一个非常简洁但挺难懂的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Getnext(int next[],string t)
{
    int j = 0,k = -1;
    next[0] = -1;
    while(j<t.length() - 1)
    {
        if(k == -1 || t[j] == t[k])
        {
            j++;k++;
            next[j] = k;
        }
        else k = next[k];
    }
}

这段代码前面先讲next[0] = -1，原因和上面一样，然后先判断k是否等于-1，k就是指代的位置（下标），k = -1意味着是第一位，不用管是否相等直接往下一位匹配，从第二位开始，此时k = 0, 意味着没匹配上则从0下标位置开始匹配。t[k]不止代表了t[k]本身，还代表了k之前的字符也都匹配了，t[j]代表 正在计算字符 之前的字符，如果t[j] == t[k]，则意味着又一位匹配上了，首先我们把j和k都向前推一位，然后这个字符的next值就应该等于现在的k值，因为k代表了开头有多少位的字符和正在计算字符前的字符一样，我们假设if一直成立，比如aaaaaaa这个串，它的next数组的值为：-1 0 1 2 3 4 5。

其实当t[j] == t[k] 时，就相当于t[j]前的k个字符（包括t[j]）可以被t[k]前的k个字符（包括t[k]）所替换。我们都是先计算好有多少个字符相等，然后把这个相等的数放到下一个字符的next里。

但是如果没匹配上的话，就有一句k = next[k]，此时我们先不管后面的next值，我们先关注如何更新k值，首先现在的情况是失配了，那么就说明前k位字符已经和后面的不相等了，那么这么长的不相等，我们找一个短的试试，因为此时t[0]~t[k-1]还是和j前面的字符相等的，我们那么t[j]前的几个字符（不包括t[j]）就和t[k]前的几个字符(不包括t[k])一样，而next[k]代表了k之前的几个字符和开头的字符相等的个数，在这里刚好就是j之前的几个字符和开头的几个字符相等的个数，这个个数比当前的k小，所以我们是退而求其次找到了一个比k小的字符的数量来重新试验能不能匹配，能匹配就继续，不能匹配我们在找一个更小的，直到找到开头。

实质上是比较当前字符的前面的字符向前和开头的字符向后的个数一样的数量，如果没匹配上的话就会测试一个更短的数量，这不一定能保证匹配，但一直找总会找到或者k = -1。

参考资料

KMP算法—终于全部弄懂了 https://blog.csdn.net/dark_cy/article/details/88698736