KMP算法详解

KMP算法作为一个效率比较高的模式匹配算法被广泛使用，但是KMP算法的效率究竟高在哪呢？

首先我们观察朴素的模式匹配算法：

我们使用text代指源字符串，pattern代指模式串

若text=aaaacdeaaab pattern=aaab

索引	0	1	2	3	4	5	6	7	8	9	10
text	a	a	a	a	c	d	e	a	a	a	b

索引	0	1	2	3
pattern	a	a	a	b

匹配过程如下：

text中匹配开始点	i	j	描述
0	0	0	匹配成功
0	1	1	匹配成功
0	2	2	匹配成功
0	3	3	匹配失败
1	1	0	匹配成功
1	2	1	匹配成功
1	3	2	匹配成功
1	4	3	匹配失败
2	2	0	匹配成功
2	3	1	匹配成功
2	4	2	匹配失败
3	3	0	匹配成功
3	4	1	匹配失败
4	4	0	匹配失败
5	5	0	匹配失败
6	6	0	匹配失败
7	7	0	匹配成功
7	8	1	匹配成功
7	9	2	匹配成功
7	10	3	完全匹配成功

很明显在失配后i需要回到开始点重新进行匹配，因此总的匹配时间复杂度为O(nm)

我们再观察另一个例子：

索引	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
text	a	b	c	a	b	c	x	a	b	c	a	b	c	a	b	c	d

索引	0	1	2	3	4	5	6
pattern	a	b	c	a	b	c	d

可以观察到，按照朴素方法，当i=6且j=6时会发生失配（此时text中的匹配开始点为0），此时按照一般思路，就会让i变成1，j变成0重新开始匹配

当前匹配状态：

索引	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
text	a	b	c	a	b	c	x	a	b	c	a	b	c	a	b	c	d
pattern	a	b	c	a	b	c	d

但是我们可以观察到一点：pattern以索引5位结尾的后缀“abc”与pattern的前缀”abc“一致，同时由于在pattern中到6的位置才适配，所以3~5肯定已经和text中的i指示的当前位置的前3个字符匹配，因此我们没必要从头开始匹配，显然可以调整j为3，从pattern索引为3的字符处开始比较，也就是如下图所示：

索引	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
text	a	b	c	a	b	c	x	a	b	c	a	b	c	a	b	c	d
pattern				a	b	c	a	b	c	d

在这种情况下，通过判断前缀后缀匹配关系，从而节省了很多次无用的比较，因此相对于朴素算法而言，这种情况匹配更快一些

我们在看另外一种情况：

索引	0	1	2
text	a	a	b
pattern	a	a

此时，a与b不一致从而适配（就是无法匹配）

此时pattern没有重复前缀，那么该怎么办呢？

很简单，直接拿pattern[0]和text[1]比较，此时也可以看做拥有空的重复前缀

从而变成下面这样：

索引	0	1	2
text	a	a	b
pattern		a	a

我们再来看一种情况：

索引	0	1	2	3
text	a	d	a	b
pattern	a	b

这个例子，很明显，根据上面那个例子可以知道，此时，pattern将滑动成这样：

索引	0	1	2	3
text	a	d	a	b
pattern		a	b

显然这时候text[1]和pattern[0]依然不一致，那么接下来又该如何做呢？

显然，由于pattern[0]之前已经没有可用于比对的字符了，也就是text[1]无法作为开始点，所以应该将i加一，从而变成如下的情况：

索引	0	1	2	3
text	a	d	a	b
pattern			a	b

最终匹配完成

我们归纳一下子串匹配的方法：

若当前两个字符相同，则推进i,j

若当前两个字符不同，且j>0，则i保持不变，j跳回pattern前缀的下一个位置

若当前两个字符不同，且j=0，则推进i

上面的方法依赖于前缀的查找，那么，我们该如何快速的找到前缀呢？

答案是构建一个叫做next的数组，数组第i项表示匹配到pattern第i+1个字符时如果失配时的pattern后缀对应pattern前缀的下一个字符的索引

例如对于

索引	0	1	2	3
pattern	a	b	a	b

对应的next数组如下：

索引	0	1	2	3
pattern	a	b	a	b
next	0	0	1	2

显然，若匹配到索引为1的字符时失配，此时的后缀只有“a”和ε（希腊字母epsilon，这里表示空串），这里要注意，前缀不能是后缀（也就是说，两个字符串不能内容相等的同时在pattern中的起始点也相同），否则j就无法向前跳（对于上述pattern来说，next[0] = 1，这样会形成一个死循环，j没有发生移动），所以在pattern中不存在前缀“a”，仅存在前缀ε，因此next[0]=0（ε的后一个字符的索引当然是0）

若匹配到索引为2的字符时失配，与上面同理，所以next[1] = 0

若匹配到索引为3的字符时失配，显然，此时存在四个后缀“a”“ba”“aba” ε，而pattern在字符3之前存在前缀“a”“ab”“aba” ε，排除掉一样的"aba"，就剩"a"和ε了（事实上，上述两个ε的位置并不一样，一个在索引0之前，另一个在索引2与3之间）

本着前缀最长的原则（因为这时候可以保持最大的已匹配状态，减少匹配次数），显然选择前缀"a"，那么，下一个匹配字符就必定是pattern[1]了，因此next[2] = 1

那么如果索引为0的字符失配怎么办？这个问题在讲子串匹配的方法的时候就提到了：若当前两个字符不同，且j=0，则推进i

next数组的定义讲完了，那么该如何求出next数组呢？

事实上可以通过pattern与自身匹配的方法来实现：

索引	0	1	2	3	4	5	6	7
pattern	a	b	a	b
pattern		a	b	a	b
next	0	0

此次失配，同时由于失配的并不是pattern的第一个字符，此时相同的前缀和后缀仅为 ε，因此若j+1个字符失配，必须跳到j=0时进行比较，即next[j] = 0

索引	0	1	2	3	4	5	6	7
pattern	a	b	a	b
pattern			a	b	a	b
next	0	0	1

此时我们相当于找到了一个相同的前缀和后缀（“a”与“a”），根据next数组定义，若第j+1个字符失配，则应跳回相同前缀的后面一个字符，因此，显然next[i] = j + 1（后缀由i-j开始由i结束，前缀由j结束，此时i=2，j=0）

索引	0	1	2	3	4	5	6	7
pattern	a	b	a	b
pattern			a	b	a	b
next	0	0	1	2

此时我们相当于找到了一个相同的前缀和后缀（“ab”与“ab”），根据next数组定义，若第j+1个字符失配，则应跳回相同前缀的后面一个字符，因此，显然next[i] = j + 1（后缀由i-j开始由i结束，前缀由j结束，此时i=3，j=1）

我们依据上述的方法可以获得next数组，时间复杂度为O(n)，同时利用next数组进行查找时间复杂度为O(m)，因此总共的子串查找时间复杂度为O(n + m)，额外的空间复杂度为O(n)

那么，进行查找的时间复杂度是否真的是O(m)？

我们观察下面一个pattern：

索引	0	1	2	3
pattern	a	b	c	d
next	0	0	0	0

那么，在匹配时，若在任意一个字符处失配，都会回退一次（回退到j=0的情况，除了j=0时），假若在text中除了最后四个字符是abcd，前面都是ax的形式，那么总回退次数显然是\frac{m-4}{2}，总比较次数显然是\frac{m-4}{2}+m=\frac{3m-4}{2}=1.5m-2（源字符串每个字符都要比较一次，回退额外比较一次)

我们再观察下面一个pattern：

索引	0	1	2	3	4	5	6	7	8
pattern	a	a	a	a	a	a	a	a	b
next	0	1	2	3	4	5	6	7	8

如果匹配时每次都在pattern的最后一个字符失配，每次失配都会产生9次回退，那么会不会让KMP算法的查找时间复杂度从O(m)降到O(mn)呢？

我们拥有这样一个事实：pattern可以回退正是因为pattern曾经推进，而pattern的推进是由于text的推进，因此总pattern的回退次数不会超过m

即总比较次数不会超过2m，该结论也可以应用到next数组的构建算法，即构建算法次数不会超过2n，因此KMP的总比较次数（包括next构建和子串比较）不会超过2n+2m次

因此KMP的时间复杂度确实是O(n+m)

实际上由上述说明还可以获知：字符串比较次数的增多正是由于pattern中存在较多的重复子串，因此对于同样的text而言，无重复字符的pattern在KMP算法中是最快的，这种子串相对于朴素算法的提速是最明显的

这里提供到leetcode上的相关题目以及我的实现代码：

力扣

class Solution 
{
public:
    int strStr(string haystack, string needle) 
    {
        if(haystack.length() <= 0)
        {
            if(needle.length() <= 0)
            {
                return 0;
            }
            else
            {
                return -1;
            }
        }

        if(needle.length() <= 0)
        {
            return 0;
        }
        else if(haystack.length() <= 0)
        {
            return -1;
        }

        int next[needle.length()];
        int i,j;

        next[0] = 0;

        for(i = 1,j = 0;(i < needle.length()) && (j < needle.length());)
        {
            if(needle[i] == needle[j])
            {
                next[i] = j + 1;
                i++;
                j++;
            }
            else if(j == 0)
            {
                next[i] = 0;
                j = 0;
                i++;
            }
            else
            {
                j = next[j - 1];
            }
        }

        for(i = 0,j = 0;(i < haystack.length()) && (j < needle.length());)
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else if(j == 0)
            {
                j = 0;
                i++;
            }
            else
            {
                j = next[j - 1];
            }
        }

        if(j < needle.length())
        {
            return -1;
        }
        else
        {
            return i - needle.length();
        }
    }
};