大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
近日,一同学面试被问到字符串匹配算法,结果因为他使用了暴力法,直接就跪了(如今想想这种面试官真的是不合格的,陈皓的一篇文章说的非常好,点击阅读)。字符串匹配方法大概有:BF(暴力破解法), 简化版的BM,KMP,BM,普通情况下,大家听说最多的应该就是KMP算法了。之前学习过,因为时间间隔比較大,记不太清楚了,今天上网查了下,发现写KMP的文章是不少,可是真正清楚简洁就没有了(july的文章太繁琐),所以自己就研究了一晚上,弄清楚了kmp的计算过程,也就在此分享下。
1. 假设你如今全然不知道KMP是个神马玩意,请先阅读 阮一峰 的《字符串匹配的KMP算法》。
//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]; } }
//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; }
本篇文章主要关注next数组的计算及kmp主算法的实现。
要了解next数组是什么?
为什么要这么计算next数组?
參见下一篇文章(字符串匹配之KMP算法(续)—还原next数组 )
.
假设你认为本篇对你有收获,请帮顶。
swalge
或者扫描下方二维码关注我
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118913.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...