站长工具seo综合查询腾讯,网站建设开发详细步骤流程图,网站收录量,wordpress图片切换插件PS#xff1a;文章是转载的 下方的微信公号不是我的 是原作者的。附上原文链接#xff1a;字符串匹配之KMP jeliy王的博客 近日#xff0c;一同学面试被问到字符串匹配算法#xff0c;结果由于他使用了暴力法#xff0c;直接就跪了(现在想想这样的面试官真的是不合格的文章是转载的 下方的微信公号不是我的 是原作者的。附上原文链接字符串匹配之KMP jeliy王的博客 近日一同学面试被问到字符串匹配算法结果由于他使用了暴力法直接就跪了(现在想想这样的面试官真的是不合格的陈皓的一篇文章说的很好点击阅读)。字符串匹配方法大概有BF(暴力破解法), 简化版的BMKMPBM一般情况下大家听说最多的应该就是KMP算法了。之前学习过由于时间间隔比较大记不太清楚了今天上网查了下发现写KMP的文章是不少但是真正清晰简洁就没有了(july的文章太繁琐)所以自己就研究了一晚上弄清楚了kmp的计算过程也就在此分享下。
1. 如果你现在完全不知道KMP是个神马玩意请先阅读 阮一峰 的《字符串匹配的KMP算法》。 KMP算法最难理解的是就是next数组的计算过程在此分享下我所理解的kmp算法以及next数组的计算过程(如果看前面理论比较头大可以先看后面例子的计算过程在回过头来看理论就会释怀) 1. next数组的计算过程: 申明:next数组下标从0算起, 定义next[0]-1, next[1]0; 模式串记为T[ ] 假如求 T中 j1 位的next[j1] 将其 前一位(模式字符)的内容与其前一位的next值(next[j])的内容(T[next[j]])进行比较 如果它们相等(T[j]T[next[j]])则next[j1] next[j]1; 如果他们不相等则继续向前寻找直到找到next值对应的内容与前一位相等为止则在这个next值上加一 如果直到第一位都没有与之相等则next[j1] 0; 例: 有模式串 abaababc j0时next[0] -1 ; j1时next[1] 0; j2时t1!t0, knext[0]-1, next[2]0; j3时t2t0, next[3] next[2]1 1; j4时knext[3]1, t3!T[1], knext[1]0, T[3]T[0], next[4]next[1]1 1; j5时knext[4]1, T[4]T[1], next[5]next[4]12; j6时knext[5]2, T[5]T[2], next[6]next[5]13; j7时knext[6]3, T[6]!T[3], knext[3]1, T[6]T[1], next[7]next[3]1 2; 2. 上述算法的实现 //update 2014-04-19 10:08 void calNext(const char *T, int *next){ int n strlen(T); if(n0) return ;next[0] -1;next[1] 0; int j0, k-1; while(jn){ if(k-1 || T[j]T[k]){j;k;next[j] k;} else k next[k];}} 3. KMP主算法 设置比较起始下标: i0, j0; 循环直到 imn 或者 T中所有字符都以比较完毕 a. 如果 S[i]T[j], 则继续比较S和T的下一个字符; 否则 b. 将 jnext[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(SNULL || TNULL) return -1; int n strlen(S); int m strlen(T); int next[m];calNext(T, next); int i0, j0; while(imn){ for( ; jminS[i]T[j]; i, j) ; if(jm) return i-m;j next[j]; if(j-1){i;j;}} return -1;} 举例 设主串 Sababcabcacbab, 模式 Tabcac 按照上述方法计算得next[]{-1,0,0,0,1} 本篇文章主要关注next数组的计算及kmp主算法的实现。 要了解next数组是什么 为什么要这么计算next数组? 参见下一篇文章(字符串匹配之KMP算法续---还原next数组 ). 如果你觉得本篇对你有收获请帮顶。另外我本人开通了微信公众号--分享技术之美我会不定期的分享一些我学习的东西. 你可以搜索公众号swalge或者扫描下方二维码关注我 转载文章请注明出处: http://blog.csdn.net/swagle/article/details/23969683 )
