数据结构与算法—KMP算法

串的模式匹配算法

子串（模式串）的定位操作通常称为串的模式匹配。

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。

串的顺序存储实现

    #include<stdio.h>
    #include<string.h>
    #define MaxLen 256  /*定义能处理的最大的串长度*/
    typedef struct {
        char str[MaxLen]; 
        int  curlen;  /*定义当前实际串长度*/
    }SString;

BF算法设计思想：

将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。
直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0

    int Index(SString *s,SString *t) 
    { * 返回子串t在主串s中的位置。若不存在，则函数值为-1*/   
       int i,j;  i=0; j=0; 
       while(i<s->curlen &&j<t->curlen) {    
           if(s->str[i]==t->str[j]) 
           {  i++; j++;  } 
           else /* 指针后退重新开始匹配 */
           {  i=i-j+1; j=0;  } 
         }
         if(j>=t->curlen) 
             return i-t->curlen+1; 
         else
             return -1;
    }

若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为：

最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次.

但一般情况下BF算法的时间复杂度为O(n+m)

模式匹配的一种改进算法——KMP

KMP算法的基本思想：每一趟匹配完成后，利用上一趟匹配的结果，将模式向右滑动尽可能远的一段距离。

其方法是：不回溯指针i，找出主串中第i个字符应和模式串的第几个字符比较。

显然next[j]只与模式串有关，与主串无关

KMP算法实现

    int Index_KMP(SString *s, SString *t)
    {
       int next[100],i=0,j=0,v;
       getnext(t,next);/*先求得模式串的next函数值*/
       while(i<s->curlen && j<t->curlen){
          if(j==-1 || s->str[i]==t->str[j])
          { i++; j++;}
          else j=next[j]; /*i不变，j回退*/
       }
       if(j>=t->curlen)
           v=i-t->curlen+1; /*匹配成功*/
       else
           v=-1;   /*匹配失败*/
       return v;
    }

求next:

    void getnext(SString *t, int *next)
    {  /*串t即作为目标串又作为模式串*/
        int j,k;
        j=0;k=-1;next[0]=-1;
        while(j<t->curlen-1)  {
           if(k==-1||t->str[j]==t->str[k]) {
              j++;k++;
              if(t->str[j]!=t->str[k])
                  next[j]=k;
              else
                  next[j]=next[k];
           }
           else k=next[k];
        }
    }

推荐参考：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

Boyer-Moore 字符串匹配算法
https://www.cnblogs.com/gaochundong/p/boyer_moore_string_matching_algorithm.html

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文