Kmp算法详解

     先说一下为啥要了解kmp算法,因为阿里面试有道面试题目,如果在所有字符串最快速度找出目标字符串的位置。我用了最暴力算法,即:

     被查找字符串和目标字符串比较的时候,当匹配到目标字符串的第一个字符的时候,若中间一个字符不匹配的话,则被查找字符串和目标字符串都需要重新回溯。如下,时间复杂度自然是M * N

        a b c d a b e f g h p b c d b h  (M个)

           b c d f  (f找不到)                      (N个)  

               b c d f (重新回溯)


     下面引入到KMP算法,例如: 搜索关键词 ABCDABD ,目标串 BBC ABCDAB ABCDABCDABDE

     1 首先找出关键词ABCDABD的特征,也就是如何找出它的部分匹配值:

                                前缀                                后缀                   公共子串的长度

             A                         x                                    x                                0

            AB                        A                                    B                               0

            ABC                    AB A                                BC C                         0

            ABCD                ABC AB A                 BCD  D  CD                       0

            ABCDA              ABCD ABC AB A     A  DA CDA BCDA               1

            ABCDAB            ABCDA ABCD         B AB DAB CDAB                2

                                        ABC AB A                BCDAB

            ABCDABD            A AB ABC ABCD    D BD ABD DABD CDABD  0 

                                 ABCDA ABCDAB       BCDABD    

        即关键词每个字母的匹配值,如下

2  寻找字符串的位置

        步骤1 (斜线部分表示不匹配):

            (1) BBC ABCDAB ABCDABCDABDE

                 ABCDABD

            (2)BBC ABCDAB ABCDABCDABDE

                    ABCDABD

              (3)BBC ABCDAB ABCDABCDABDE  

                        ABCDABD

               (4)BBC ABCDAB ABCDABCDABDE  

                           ABCDABD

                (5)BBABCDAB ABCDABCDABDE 

                             ABCDABD

                 步骤1中(5) D与空格不匹配,若按以前暴力的方式,则从上一次开始匹配的第一字符的下一个字符开始重新比较,效率比较低了,现在就按如下原则开始移动:

                移动的位数 = 已匹配的字符数 - 关键词匹配的最后一个词的匹配值

           步骤2

            (1)  则搜索关键词移动的位数 = 6(已经匹配 ABCDAB) - 2(最后一个值的匹配值为2) ,所以移动结果如下:

                    BBABCDAB ABCDABCDABDE

                                        ABCDABD

            (2)  以上比较C与空格不匹配,则移动的位数 = 2 (已经匹配的数目)- 0(最后一个匹配字符B的值) = 2

                     BBABCDAB ABCDABCDABDE

                                             ABCDABD

              (3)  按步骤1的方式进行匹配

                     BBABCDAB ABCDABCDABDE

                                               ABCDABD

               (4) 需要移动的位置 ,移动的位数 = 6 - 2 = 4

                        BBABCDAB ABCDABCDABDE

                                                            ABCDABD

            以上是kmp算法详解,比较简单,算是了解算法了,但是还得深究原理。也就是达到学习的what,how,但没有知道why,所以下一篇会更新why

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 9,069评论 0 13
  • 原链接:KMP算法详解|CloudWong 传统的字符串匹配模式(暴力循环) 子串的定位操作通常称作串的串的匹配模...
    简Cloud阅读 3,953评论 1 22
  • 字符串匹配KMP算法详解 1. 引言 以前看过很多次KMP算法,一直觉得很有用,但都没有搞明白,一方面是网上很少有...
    张晨辉Allen阅读 2,454评论 0 3
  • 在数据结构课上老师讲了kmp算法,但当时并没太懂,现在把思路重新理一遍。 1.kmp算法简介 KMP是三位大牛:D...
    zealscott阅读 261评论 0 1
  • 《ijs》速成开发手册3.0 官方用户交流:iApp开发交流(1) 239547050iApp开发交流(2) 10...
    叶染柒丶阅读 5,379评论 0 7