字符串匹配之KMP—全力解析

字符串匹配之KMP—全力解析

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

近日,一同学面试被问到字符串匹配算法,结果因为他使用了暴力法,直接就跪了(如今想想这种面试官真的是不合格的,陈皓的一篇文章说的非常好,点击阅读)。字符串匹配方法大概有:BF(暴力破解法), 简化版的BM,KMP,BM,普通情况下,大家听说最多的应该就是KMP算法了。之前学习过,因为时间间隔比較大,记不太清楚了,今天上网查了下,发现写KMP的文章是不少,可是真正清楚简洁就没有了(july的文章太繁琐),所以自己就研究了一晚上,弄清楚了kmp的计算过程,也就在此分享下。

1. 假设你如今全然不知道KMP是个神马玩意,请先阅读 阮一峰《字符串匹配的KMP算法》

KMP算法最难理解的是就是next数组的计算过程,在此分享下我所理解的kmp算法以及next数组的计算过程(假设看前面理论比較头大,能够先看后面样例的计算过程,在回过头来看理论就会释怀):

     1. next数组的计算过程: 
          申明:next数组下标从0算起, 定义next[0]=-1, next[1]=0; 模式串记为T[ ]
          假如求 T中 j+1 位的next[j+1]:
          将其 前一位(模式字符)的内容与其前一位的next值(next[j])的内容(T[next[j]])进行比較:
               假设它们相等(T[j]==T[next[j]]),则next[j+1] = next[j]+1;
               假设他们不相等,则继续向前寻找,直到找到next值相应的内容与前一位相等为止,则在这个next值上加一;
               假设直到第一位都没有与之相等,则next[j+1] = 0;           
           例: 有模式串 “abaababc”
          j=0时,next[0] = -1 ; j=1时,next[1] = 0;
          j=2时,t1!=t0, k=next[0]=-1, next[2]=0;
          j=3时,t2==t0, next[3] = next[2]+1 = 1;
          j=4时,k=next[3]=1, t3!=T[1], k=next[1]=0, T[3]==T[0], next[4]=next[1]+1 = 1;
          j=5时,k=next[4]=1, T[4]==T[1], next[5]=next[4]+1=2;
          j=6时,k=next[5]=2, T[5]==T[2], next[6]=next[5]+1=3;
          j=7时,k=next[6]=3, T[6]!=T[3], k=next[3]=1, T[6]==T[1], next[7]=next[3]+1 = 2;



字符串匹配之KMP---全力解析

      

     2. 上述算法的实现:
     
       //update 2014-04-19 10:08
       void calNext(const char *T, int *next){
          int n = strlen(T);
          if(n<=0) return ;
          next[0] = -1;
          next[1] = 0;
          int j=0, k=-1;
          while(j<n){
               if(k==-1 || T[j]==T[k]){
                    ++j;
                    ++k;
                    next[j] = k;
               }
               else  k = next[k];
          }
     }
     3. KMP主算法:
          设置比較起始下标: i=0, j=0;
          循环直到 i+m>n 或者 T中全部字符都以比較完成
               a. 假设 S[i]==T[j], 则继续比較S和T的下一个字符; 否则
               b. 将 j=next[j], 从这位置開始继续进行比較;
               c. 假设j==-1, 则将 i 和 j 分别加1, 继续比較;
          假设T中全部字符均比較完成,则返回匹配的起始下标,否则返回-1;
     4. KMP算法实现:

     
       //update 2014-04-19 10:08
       int kmpmatch(const char *S, const char *T){
          if(S==NULL || T==NULL) return -1;
          int n = strlen(S);
          int m = strlen(T);
          int next[m];
          calNext(T, next);
          int i=0, j=0;
          while(i+m<=n){
               for( ; j<m&&i<n&&S[i]==T[j]; ++i, ++j) ;
               if(j==m) return i-m;
               j = next[j];
               if(j==-1){
                    ++i;
                    ++j;
               }
          }
          return -1;
     }
举例: 设主串 S=”ababcabcacbab”, 模式 T=”abcac”
          依照上述方法计算得next[]={-1,0,0,0,1}


字符串匹配之KMP---全力解析



字符串匹配之KMP---全力解析


本篇文章主要关注next数组的计算及kmp主算法的实现。
要了解next数组是什么?
为什么要这么计算next数组?
參见下一篇文章(字符串匹配之KMP算法(续)—还原next数组 )

.

假设你认为本篇对你有收获,请帮顶。

另外,我本人开通了微信公众号–分享技术之美,我会不定期的分享一些我学习的东西.
你能够搜索公众号:
swalge
 或者扫描下方二维码关注我
字符串匹配之KMP---全力解析

(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/23969683 )

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118913.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号