重读KMP算法

发表于 更新于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 8 分钟

这几天看了《大话数据结构》第五章-串，重新了解了串这个数据结构，当然其中最重要的模式匹配算法KMP有了新的认识，或者说是终于理解了。
接下来结合我的理解和CSDN中大佬的详解，讲一讲KMP吧！

朴素的模式匹配（BF算法、暴力算法）

简介

这是最早、最简单的模式匹配算法，就是简单的暴力算法，思路：
* 主串S，模式串T * 从主串S第一位开始和模式串T第一位开始匹配，成功匹配返回匹配成功的第一位，匹配失败，主串S后移一位，模式串重新从头开始匹配

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//朴素的匹配,从pos位置开始匹配
int Index(string S, string T, int pos)
{
    int i = pos;
    int j = 0;
    while (i < S.length() && j < T.length())
    {
        if (S[i] == T[j])
        {
            //①如果当前字符匹配成功（即S[i] == T[j]），则i++，j++  
            ++i;
            ++j;
        }
        else
        {
            //②如果失配（即S[i]! = T[j]），令i =（i - j） + 1，j = 0  
            i = i - j + 1;
            j = 0;
        }
    } if (j == T.length())
        return i - j;
    else
        return -1;
}

例

S="goodgoogle",T="google"
>1. goodgoogle
google >2. goodgoogle
  google >3. goodgoogle
    google >4. goodgoogle
      google >5. goodgoogle
        google

朴素的模式匹配就是这个过程，可以看出这种算法的时间复杂度很大，为了优化模式匹配就有了KMP算法 # KMP算法

简介

KMP是由三位前辈研究出来的避免重复遍历的高效率模式匹配算法，它们分别是D.E.Knuth、J.H.Morris、V.R.Pratt。知道了吧KMP是来自这三位前辈的名字，我们在称之为克努特-莫里斯-普拉特算法。 # 原理

通俗的讲，KMP算法利用已匹配的现有信息，省去不必要的匹配过程，进而优化算法。
>先上一个例子解释一下
S="abcababcax",T="abcabx"
>1. abcababcax
abcabx
>2. abcababcax
  abcabx
>3. abcababcax
    abcabx
>4. abcababcax
      abcabx
>5. abcababcax
      abcabx
>6. abcababcax
      abcabx

1前5位“abcab”匹配成功，此时S的第i位"a"与T的第j位"x"匹配失败，i=5，j=5，按照朴素的模式匹配算法，接下来要让T串后移一位继续与S匹配，i变为1，j变成0，就是上面的过程，其实从1获取的匹配信息可以知道S的前三位"abc"已与T的相应位匹配成功，且"bc"并不等于"a"，所以23步不可能匹配成功，i在第一步时已经等于5了，但经过2345过程5->1->2->3->4->5最后S的第i位"a"与T的第j位"c"匹配失败,i=5，j=2。可以发现之前的2345可以去掉，i在这变化中又回到5，这个过程变化的好像只是j的值，KMP要做的就是省去不必要的匹配过程，直接跳到合适的位置。 # 代码

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
//KMP
int KmpSearch(string S, string T, int pos)
{
    int i = pos;
    int j = 0;
    int Sl = S.length();
    int Tl = T.length();
    while (i < Sl && j < Tl)
    {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == T[j]），都令i++，j++
        if (j == -1 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且当前字符匹配失败（即S[i] != T[j]），则令 i 不变，j = next[j]    
            //next[j]即为j所对应的next值      
            j = next[j];
        }
    }
    if (j == Tl)
        return i - j;
    else
        return -1;
}

next数组

前面提到合适的位置，什么叫做合适的位置呢，就是主串S与模式串T失配时，i不变，只移动模式串T到合适的位置再与S匹配，这个合适的位置就存在next数组中。
上例中第一次在i=5，j=5失配，省去不必要的过程后i=5，j=2，也就是i不变，j从5变成2，这个过程中省去的是T前两位"ab"与S的45位"ab"匹配的过程，省去的原因是在第一次已经匹配过了，S的"abcab"与T的"abcab"匹配，可以发现，T的前缀和后缀都有"ab"，则下次匹配可以从T的第2位"c"开始与S上次失配的第5位开始重新匹配。

最大相同前后缀

要计算next数组一定要知道最大相同前后缀，从上面的解释可以知道，j的变化与模式串T有关，在失配时j=next[j]，所以要知道T最大前后缀与next数组的关系。

对于模式串T="abcabx"

模式串 a b c a b x
最大相同前后缀 0 0 0 1 2 0
next数组 -1 0 0 0 1 2

串为"a"，"ab"，"abc"，时最大相同前后缀为0，"abca"为1及前后的"a"，"abcab"为2及前后的"ab"。把next 数组跟求得的最大相同前后缀对比后，不难发现，next 数组相当于“最大相同前后缀” 整体向右移动一位，然后初始值赋为-1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//next数组
void GetNext(string T, int next[])
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j <T.length() - 1)
    {
        //T[k]表示前缀，T[j]表示后缀
        if (k == -1 || T[j] == T[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

代码有点难理解，我简单解释一下，这里涉及了已知next[0,...,j],求next[j+1]的问题。
> 对于T的前j+1个序列字符：

  • 若T[k] == T[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
  • 若T[k ] ≠ T[j]，如果此时T[ next[k] ] == T[j ]，则next[ j + 1 ] =  next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符T[j+1]之前不存在长度为k+1的前缀"T0 T1, …, Tk-1 Tk"跟后缀“Tj-k Tj-k+1, …, Tj-1 Tj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “T0 T1, …, Tt-1 Tt” 等于长度更小的后缀 “Tj-t Tj-t+1, …, Tj-1 Tj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行T串前缀跟T串后缀的匹配。
  • 原文链接：https://blog.csdn.net/v_JULY_v/article/details/7041827

next数组的优化

问题的出现

后来有人发现，KMP算法还是有缺陷的。
如果用之前的next 数组方法求模式串“abab”的next 数组，可得其next 数组为-1 0 0 1（0 0 1 2整体右移一位，初值赋为-1），当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串j = next[j] =1。 > abacabababc
abab

右移2位后，b又跟c失配。事实上，因为在上一步的匹配中，已经得知p[3] = b，与s[3] = c失配，而右移两位之后，让p[ next[3] ] = p[1] = b 再跟s[3]匹配时，必然失配。
> abacabababc     abab

问题出在不该出现T[j] = T[ next[j] ]。为什么呢？理由是：当T[j] != S[i] 时，下次匹配必然是T[ next [j]] 跟S[i]匹配，如果T[j] = T[ next[j] ]，必然导致后一步匹配失败（因为T[j]已经跟S[i]失配，然后你还用跟T[j]等同的值T[next[j]]去跟S[i]匹配，很显然，必然失配），所以不能允许T[j] = T[ next[j ]]。如果出现了T[j] = T[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。
原文链接：https://blog.csdn.net/v_JULY_v/article/details/7041827

代码

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
//优化过后的next 数组求法
void GetNextval(string T, int next[])
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < T.length()- 1)
    {
        //T[k]表示前缀，T[j]表示后缀  
        if (k == -1 || T[j] == T[k])
        {
            ++j;
            ++k;
            //较之前next数组求法，改动在下面4行
            if (T[j] != T[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现T[j] = T[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

KMP算法时间复杂度分析

朴素的模式匹配算法时间复杂度分析如下：（n为主串长度 ，m为模式串长度）

情况 时间复杂度 备注
最好情况 O(1) 一开始就匹配成功
最坏情况 O((n-m+1)*m) 每次不成功的匹配都发生在模式串的最后一个字符
平均情况 O(n+m) 根据等概率原则，平均是(n+m)/2次查找

总结

数据结构是非常重要的，这次的KMP算法也是花了好久才理解的。
欢迎批评指正。