KMP Algorithm

KMP 算法

KMP算法是子串搜索算法中最有效、最有名的一个算法，它有效地减少了匹配子串时的比较次数，降低了时间复杂度，其中蕴含算法的思想更是值得学习的。

暴力子串搜索算法

步入正题之前，让我们先来看看最简单的子串搜索算法，分析其问题的所在。

暴力子串搜索就是采用双循环，先比较主串和模式串的第一位，再比较第二位，以此类推，直至比较结果不匹配，则主串前移，继续重复上述过程，；若直至模式串末位都匹配，则找到目标。

程序组织如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int Search(string main_str, string pattern_str)
           {
               int m = main_str.Length;
               int n = pattern_str.Length;
               int target = -1;
               for (int i = 0; i < m-n; i++)
               {
                   for (int j = 0; j < n; j++)
                   {
                       if (main_str[i+j]!=pattern_str[j])
                       {
                           break;
                       }
                       if (j == n - 1)
                       {
                           target = i;
                       }
                   }
               }
               return target;

           }

暴力子串搜索算法的分析

可以看到，以这种方式进行搜索，在最坏的情况下要进行n(m-n)次运算，所以它的时间复杂度为O(n(m-n))，当数据量很大的时候，此种算法的效率很低。

KMP算法

在前面我们看到暴力法搜索会耗费很多的时间，那么该如何改进呢？如果要减少运算次数，那么必须减少循环的次数，也就是不能一个一个的比较，我们希望第二次搜索可以在第一次的基础上，从最优的位置继续开始循环。也就是说，我们要充分利用前一次搜索失败的信息。下面我们来具体分析如何利用上一次搜索的信息：

KMP算法的关键——next()函数

初步分析

mark

如图，在每次不匹配时，我们可以利用前面的信息来移动模式串（实际上我们可以知道匹配开始点到不匹配点之间主串的字符），图中第一次匹配在第五个位置匹配失败，则我们可以知道主串前四位是abda，那么我们可以知道模式串向右移动1、2位都是不匹配的，因此应该移动3位，即移动到第二个a的位置。由此我们可以猜测每次匹配失败时，模式串向右移动的最佳长度和模式串自身的结构和失败的位置有关，即是关于模式串序号的一个函数。我们把这个函数记为next（i），下面是一个示例。

mark

通过上面的示例以及分析我们可以知道，如果记模式串匹配失败前的内容为P(i),则我们希望找一个k使得P(i)的前k项和后k项是一样的，并且这个k是满足上面的条件中最大的那个，也就是说我们想找到一个P(i)的前缀，它也是模式串的后缀，并且长度是最大的，这个长度就是k。

深入分析

上面我们得到了next（i）的求解方法，下面我们来分析一下为什么是这样的。

mark

假设这是一次匹配，它将在序号为9的地方匹配失败，那么下一次匹配的时候我们应该将模式串移动到什么位置呢？显然模式串的开头是a，那么模式串一定得移到主串中a的位置（3,4,6）。如果模式串移动到3的位置，那么如下图

mark

我们可以看到这种情况是不匹配的，因为从上一次的匹配中我们可以知道主串4位置是a，与b不匹配，移动到位置4的情况相同。

我们把问题抽象出来就是这样的

第一次匹配后，我们所知道的主串是这样的

mark

而模式串是这样的

mark

现在需要移动模式串进行第二次匹配，由于这种情况不好看清本质问题，所以我们假设第一次匹配后情况如下

mark

mark

图中，匹配失败处i=11，并且P(i)实际上就是主串已知的内容。由上面的讨论，我们可以知道模式串移动到3,5的位置是不匹配的，在这里我们可以知道为什么next（i）要找P(i)最长的前缀（同时是后缀），因为如果模式串移动到一个以a（模式串的第一个字符，这里是a）开头但不是后缀的地方，如5的位置（参照下图），虽然前五个abcab是匹配的，但是第六个字符主串是c而模式串是a,换言之处于中间的以a开头的位置需要确保其后的每一个字符与模式串对应位置是匹配的,直到主串序号i之前，那么满足这样条件的一定是P(i)的一个后缀（因为上述条件保证了P(i)的一个后缀与模式串的一个前缀对应相等，而模式串的前缀一定也是P(i)的前缀，所以我们找的是P(i)中既是前缀又是后缀的字符串，理论上符合这样条件的都可以作为模式串移动的依据，但是为了尽可能的充分利用已知信息，我们应该找寻最长的那个前/后缀）

mark

由此我们正式给出next(i)的定义

next函数计算的递推法

为了实现递推，我们把next(0)记为0，并记next(i)=$k_{i}$，那么递推关系如下：

  1. 当P(i)=p($k_{i}$)时，$k_{i+1}$=$k_{i}+1$

  2. 当P(i)$\not=p(k_{i}$)时,

递推法的详析

下面先给出一个例子

mark

毫无疑问，next(1)一定为零（只有一个字符），next(2)也为零，next(3)等于1。

next(4)等于1可以这么计算：由于p(4)只比p(3)多了一个a，并且已知p(3)最长前后缀长度为1，那么只要比较p(4)的第一位（序号从零开始）与新增的那位是否相等，若相等，则next(4)=next(3)+1应该是显然的，若不等，并不能说next(4)=0，实际上next(4)也不为零。

因为新增位与最长前缀的下一位不相等，只能说明next(4)的值不可能大于或等于next(3)，但是可能是小于next(3)的某个值。那么应该如何计算next(4)的值呢？请看下图

mark

我们来观察next(10)的计算，p(10)新增的b与p(9)第六位的a，不同，所以next(10)<6，现在我们任想找最长的前后缀，当然可以通过循环比较的方法来寻找，但是我们希望能充分利用已知的信息来简化计算。

刚才我们在已知最长前后缀abaaaba的基础上来比较下一位是否相等，结果不相等，自然而然，我们接下来应该找一个短一点的前后缀，再去比较这个短一点的前后缀的下一位是否相等，并且利用已知的条件可以很高效的找出这个短一点的前后缀，详析见下图

mark

KMP算法的组织

与暴力求解不同，在KMP算法中，我们希望仅用一个循环来解决问题。循环变量为主串的下标，第一次匹配时，模式串下标自增，当匹配失败时，模式串的下标由next(i)函数来确定，然后继续与主串进行匹配。这样就比避免了每次匹配失败时模式串下标的回溯。

模式串的下标与next(i)的关系：下标=next(i)

KMP的程序实现

  1. next函数的实现，程序如下

    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    class Program
       {
           static void Main(string[] args)
           {
               //这是一个测试
               int[] nextarray = Next("ababababca");
               foreach (var item in nextarray)
               {
                   Console.Write(item + " ");
               }
               Console.Read();
           }
       
           public static int[] Next(string pattern_str)
           {
               int len = pattern_str.Length;
               int[] next = new int[len];
               //next数组的第0,1位一定是零
               next[0] = 0;
               next[1] = 0;
               for (int i = 2; i < len; i++)
               {
                   //P(i)新增的字符与P(i-1)最长前缀的后一位匹配时的情况
                   if (pattern_str[i - 1] == pattern_str[next[i - 1]])
                   {
                       next[i] = next[i - 1] + 1;
                   }
                   else
                   {
                       //P(i)新增的字符与P(i-1)最长前缀的后一位不匹配时，寻找更小的前后缀，并继续比较p(i)新增字符与新的前缀的后一个字符是否相等，相等，计算next(i)；不等，继续寻找更小的前后缀。
                       int j = next[i - 1];
                       while (j >= 0)
                       {
                           j = next[j];
                           if (pattern_str[j] == pattern_str[i - 1])
                           {
                               next[i] = j + 1;
                               break;
                           }
                           else
                           {
                               //若最小的前后缀都无法使其后一位与P(i)新增的字符相等，则说明P(i)不存在前后缀，next(i)=0.
                               if (j==0)
                               {
                                   next[i] = 0;
                                   break;
                               }
                           }
       
                       }
                   }
               }
               return next;
           }
       }

    运行上面的程序，我们将得到下面的结果

    mark

    我们可以看到输出结果与前面计算的一样，为保证算法的准确性，使用字符串”abaabaababb”再次进行验证，得到如下输出

    mark

    经验证，与计算结果一致，则程序基本无误。

  2. 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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine(KMP("abdadabdabadabdabbb", "abdabb"));
                Console.Read();
            }
            public static int KMP(string main_str, string pattern_str)
            {
            //初始化工作，获取主串、模式串长度；计算next数组，循环变量初始化，结果初始化（无匹配的返回值）
                int main_len = main_str.Length;
                int pattern_len = pattern_str.Length;
                int j = 0;
                int target = -1;
                int[] next = Next(pattern_str);
                int i = 0;
                //主循环为主串下标的自增
                while (i < main_len)
                {
                //判断主串字符和模式串字符是否相等
                    if (main_str[i] == pattern_str[j])
                    {
                    //若模式串下标已经达到最大，匹配成功，退出循环
                        if (j == pattern_len - 1)
                        {
                        //此时的i为匹配成功末位的值，需要减去模式串的长度再加一才是匹配成功首位的位置
                            target = i-pattern_len+1;
                            break;
                        }
                        else
                        {
                            j++;
                        }
                        i++;
                    }
                    else
                    {
                    //如果j=0并且进入这个else说明模式串首位与主串i处不匹配，主串序号需要加一，否则下一次循环j还是0，会陷入循环比较
                        if (j == 0)
                        {
                            i++;
                        }
                        //由next数组求得下一次j的值
                        j = next[j];
                    }
                }
                return target;
            }

    //next数组的求解
            public static int[] Next(string pattern_str)
            {
                int pattern_len = pattern_str.Length;
                int[] next = new int[pattern_len];
                next[0] = 0;
                next[1] = 0;
                for (int i = 2; i < pattern_len; i++)
                {
                    if (pattern_str[i - 1] == pattern_str[next[i - 1]])
                    {
                        next[i] = next[i - 1] + 1;
                    }
                    else
                    {
                        int j = next[i - 1];
                        while (j >= 0)
                        {
                            j = next[j];
                            if (pattern_str[j] == pattern_str[i - 1])
                            {
                                next[i] = j + 1;
                                break;
                            }
                            else
                            {
                                if (j == 0)
                                {
                                    next[i] = 0;
                                    break;
                                }
                            }

                        }
                    }
                }
                return next;
            }
        }

    我们用给出的第一个例子来验证这个算法，得到结果为

    mark

经过验证，匹配成功的首位确为12处，程序无误。

KMP算法分析

从程序的实现可以看出，算法可以分为两部分：next函数计算和匹配过程。其中，next函数的计算的时间复杂度为O(m1)，并且可以证明next函数计算耗费不会超过2m；而匹配的过程显然时间复杂度为O(n2)，并且可以证明匹配计算耗费不会超过2n。（具体证明限于篇幅，此处仅给出结论）

综上，KMP算法的时间复杂度为O(m+n)，是线性的，远小于暴力法的O((m-n)*n)

1. m为模式串的长度 ↩
2. n为主串的长度 ↩

本文标题:KMP Algorithm

文章作者:ZhuMing

发布时间:2019-07-09, 14:23:32

最后更新:2019-08-02, 22:54:28

原始链接:http://zhumingcj.github.io/2019/07/09/kmp-algorithm/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. KMP 算法
  2. 2. 暴力子串搜索算法
    1. 2.0.0.1. 暴力子串搜索算法的分析
  • 3. KMP算法
    1. 3.0.0.1. KMP算法的关键——next()函数
      1. 3.0.0.1.1. 初步分析
      2. 3.0.0.1.2. 深入分析
      3. 3.0.0.1.3. next函数计算的递推法
      4. 3.0.0.1.4. 递推法的详析
  • 3.1. KMP算法的组织
  • 3.2. KMP的程序实现
  • 3.3. KMP算法分析