Sitch's Blog
0%

KMP 字符串模式匹配

发表于 分类于 Valine：

字符串模式匹配——给定两个字符串，主串 haystack，模式串 needle。在 haystack 中查找 needle 出现的首字符位置。

示例：

输入：haystack="hello",needle="ll" 输出：2

"ll" 在“hello”中出现的首字符位置是第三个字符，下标是 2

暴力的简单匹配

思想是，在 haystack 的每个位置，都检查一遍是不是 needle 的首字符，即后续能不能和 needle 匹配上。

使用两层循环很简单，时间复杂度是 O(len_h*len_n)，显然过于复杂。

简单匹配的优化方向

既然要优化，我们肯定要知道原来的算法到底在哪里浪费了性能。可以看下面的例子：

haystack="abcabcabe" needle="abcabe"

跟着简单匹配的思路，以 haystack[0] 为起点，然后主串模式串同时向后移动并匹配每一位，我们可以发现最终匹配会停留在：

  • abcabcabe
  • abcabe

即 c 和 e 匹配失败，那么简单匹配会退出这轮子循环，再以 haystack[1] 进行匹配。

此时以人的思维去看，以 b 或 c 为起点肯定匹配不成功，相反 abcabcabe 和abcabe 是显然可以匹配到的。

而且从遍历的角度来看，主串已经走到了 haystack[5]，相当于我们已经获取了前 6 位字符的信息了，我们已经知道前 6 位是什么字符了，再从 haystack[1] 开始的话就相当于刚见过人家长啥样就忘了，没有利用到已知信息，这就是问题所在。

失败返回的有效信息

匹配在 e 处失败，整理一下这次匹配获得的信息： - 主串从匹配起点到失败点，必然是 abcab，要不然肯定在前面就失败了，不会在第六位失败。

更普遍一点，在模式串 needle[i] 位失败，那么主串 haystack 在失败点前面必然有 needle[0~i-1] 的所有字符。而因为 needle 是固定不变的，所以不管 i=1，2，3，4，5 ... 主串从匹配起始点到匹配失败点间的字符，都肯定是固定的。

这就是匹配失败告诉我们的教训。

利用失败信息

例如匹配情况如下： - xxxxxx abcabd xxxxxx - abcabe

我们甚至不需要知道主串长什么样，只要模式串在 e 处失败，我们就可以闭眼预测——主串失败点前面肯定是 abcab 。

既然我们已经能预测到有 abcab 了，那么我们能做点什么呢？当然能啊，对面都明牌了，我们事先安排好最优匹配策略不就完事。

上例中已知 abcabd ，那人眼显然看出来了——a 开始的匹配失败了，b、c 开头的显然不行，abcabd 的 ab 恰好直接对上模式串前两位 ab，那我们接下来干嘛呢？当然直接从 ab 的位置接后着匹配 d 和 c： - xxxxxxxx abcabd xxxxx - abcabe

此时可以发现，主串遍历指针在 d 处失败，直接再从 d 开始，不需要回退到 b ，这是 KMP 的最大优点。

通过我们事先的预测可以发现，不管主串长什么旮旯样，只要匹配在 abcabe处失败，那么下一个匹配一定可以直接从abcabe 开始，不需要主串回退遍历。甚至不仅没回退，还在主串不同的情况下，模式串直接免掉了几位的匹配。

假如失败在第 1 位、第 2 位、... 第 i 位呢？显然前面说过，在哪一位匹配失败后，前面都有固定的字符串，我们都可以做好事先预测。

例 1： - xxxxx abcad xxxx - abcabe 此时我们知道前面是 abca，观察可知接下来的最优方案是直接以 needle[0] 对上主串的第二个 a。

例 2：

  • xxxxx abacd xxxxx
  • abace 此时我们知道前面是 abac，但即使 needle[0] 对上了主串失败区间的第二个 a，也必然会失败，因为后面是 c 和 b 的必然不匹配，我们也没必要去尝试了。

通过例 2 我们知道，匹配失败后我们拿 needle 的头部去主串中找一个地方对上，但对上的时候必须有这样一个结构：模式串前缀 axx 刚好对上主串失败区间的后缀 axx，这样的匹配才可能成功。

怎么事先预测

现在我们的目标是怎么让程序去做事先预测，只要做好了事先预测，那么每次失败之后的下一步该怎么做就知道了。

我们还知道，失败后可能成功的匹配只有 模式串前缀=失败区间后缀，而失败区间又是模式串自己的子串，因此就是模式串 0~i 的子串的前后缀相同，i 为模式串的任意位置。

具体来说，在模式串 i 位失败，假如模式串前缀 [0~k-1] 和 0~i 的后缀 [i-k~i-1] 有 k 位相同，那么直接拿前缀去匹配后缀在主串中的位置就可以了。

即：主串指针不动，前缀有 k-1 位匹配好了，模式串指针跳转到 needle[k] 继续匹配。

在这个例子中： - xxxxxxxx abcabd xxxxx - abcabe

模式串在 e 失败，则指针跳转到下标 2 的位置，以 needle[2] 去匹配 d

创建失效数组

所以我们可以创建一个失效数组，第 i 位存储模式串在第 i 位失败后，模式串指针应当跳转到的位置。

而且因为模式串固定，失败后的跳转位置也固定，做好了一个失效数组就可以在任意主串匹配中使用。

所以我们的最终问题在于，检测每个失败区间 0~i 中是否有前后缀相同的 k 位，并据此设定失败后的模式串指针跳转到 needle[k]。

当然找到前后缀相同的 k 位，其实也就是前后缀的模式匹配问题。 >... 嗯，也是模式匹配。 >KMP 让我惊叹地点在于，为了构造 KMP 的失效数组，也用到了 KMP 自身的思想 ...

前后缀计算的主要思想如下： - 前后缀的匹配有动态规划特性，0~i+1 的前后缀，直接和 0~i 的前后缀相关联。例如对于 i 位以前的 0~i-1 有 k 位成功匹配的前后缀：

- 假如 needle[k]==needle[i]，即前后缀可继续累加，0\~i 则有了 k+1 位前后缀。

- needle[k]!= needle[i]，相当于此时前后缀 i k 位匹配失败，相当于 0\~k 的子串作为模式串 needle，去模式匹配后缀的子串，结果在 k 位失败了，按照我们之前失败跳转的思想，这里 k 自然进行跳转到对应位置 lost[k]。

注意 0~i 的有效前后缀 k 位，是为第 i+1 位的失败服务的，而不是为第 i 位。换句话说，计算出了 0~i 位有 k 位有效的前后缀，那么进行 i++，然后把 k 填入 lost[i]。

构造失效数组代码，逐句详细注释： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<int> GetLost(string& needle) 
{   
    vector<int> lost(needle.size(),0);//构造等长失效数组，初始值 0
    //KMP

    lost[0]=-1;//在 0 位失败肯定没法跳跃，-1 表示退出子循环。
    int k=-1;//跳跃位置，也即匹配前缀的下一位
    int i=0;//尾部
    
    while(i<needle.size()-1)
    {
        //前缀还空着或 i k 位相同，即目前为止前后缀仍相同，可以继续累加匹配的前后缀长度。
        if(k==-1 || needle[i]==needle[k])
        {
            //因为前后缀都是相对于 i 位之前的，在 0~i-1 的有效前后缀，其实是下一位，i 位跳转需要用到的，所以 i++，k++。
            i++;
            k++;
            
            //设定在 i 位失败的跳转位置
            //i k 位不同，则就是跳转到 k。假如 i k 位相同，你说 i 失败了，k 必然也会失败，有啥意义呢，所以跳转到 k 跳转的位置。
            if(needle[i]!=needle[k])
                lost[i]=k;
            else//
                lost[i]=lost[k];
        }

        //此时前后缀 i k 位匹配失败，相当于 0~k 的子串作为模式串 needle，去模式匹配后缀的子串，结果在 k 位失败了，按照我们之前失败跳转的思想，这里 k 自然进行跳转 ... KMP 内置 KMP 嗯
        else   
            k=lost[k];
    }

    return lost;//完成失效数组
}

利用失效数组进行模式匹配

失效数组有了，每次失败后将模式串指针进行对应跳转即可，此时的模式匹配已经十分简单。

匹配代码，这里只做了一次位置查找，简单修改可以查找出所有位置： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int strStr(string& haystack, string& needle) 
{   
    int x=0;//主串指针
    int y=0;//模式串指针
    vector<int> lost=GetLost(needle);//失效数组

    //模式串匹配
    while(x<haystack.size() && y<int(needle.size())) //注意这里 int 化！！！！！！很容易出意外的 bug，因为 size 返回值是 unsigned int
    {
        if(y==-1 ||haystack[x]==needle[y])//匹配成功，或刚开始
        {
            //当前位没问题，到下一位
            x++;
            y++;
        }
        else//匹配在 y 失败，跳转到 lost[y]
        y=lost[y];
        
    }
    
    if(y==needle.size())//是模式串完全匹配成功退出循环的，x-y 即首字符位置
        return x-y;
    else//匹配失败退出循环的
        return -1;
}