工作一直做web开发,今天偶尔看到讲解算法的blog,想试试看看根据思路能否自己实现下,对算法不自信的曾经的学渣同学竟然写出来了!正好好久不写blog,发一篇证明下自己还活着。
class kmp { final static boolean isDebug = false private static List getMatMapNumber(String str){ def numList = [0] int len = str.size() str.eachWithIndex{ch, i -> // 首位是0,跳过 if(i == 0) return numList[i] = 0 String sub = str[0..i] List subPre = [] List subSuf = [] int lenSub = sub.size() for(j in 1..<lenSub){ subPre << sub[0..<j] subSuf << sub[lenSub-j..-1] } if(isDebug){ println 'For string - ' + sub println 'Pre - ' + subPre println 'Suf - ' + subSuf } String one = subPre.find{pre -> pre in subSuf} if(one) numList[i] = one.size() } numList } private static int findByMatInner(String str, String target, List numList, int beginSearch){ int i = beginSearch, j = 0, len = target.size() if(i >= str.size()) return -1 for(; j < len;){ if(str[i] != target[j]){ // 如果第一个就匹配不上,就下标 + 1,否则就下标移动的距离为“已经匹配的长度 - 最后匹配的字母对应的匹配数” int stepForward = j == 0 ? 1 : j - numList[j - 1] println j + ' - ' + stepForward // 递归查找,移动开始匹配的下标 return findByMatInner(str, target, numList, beginSearch + stepForward) } i++ j++ } return j == len ? i - len : -1 } private static int findByMat(String str, String target){ def numList = getMatMapNumber(target) findByMatInner(str, target, numList, 0) } static void main(String[] args){ String str = 'bbc abcdab abcdabcdabde' String target = 'dabc' // println getMatMapNumber(target) int index = findByMat(str, target) println index println str[index..-1] } }
相关推荐
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构
数据结构课程设计,用KMP算法实现的文本检索,检索本地文件,使用MFC,可视化界面
KMP算法实现的C++代码,KMP算法实现的C++代码,KMP算法实现的C++代码
简单的kmp算法实现,代码结构十分清晰,适合初学者理解kmp算法
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
kmp算法 kmp算法_基于Python+kmp算法实现模糊文本字符串匹配
编程求出子串(模式串)的next值,利用kmp算法实现子串与多个主串的匹配,针对同一子串next值只计算一次。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
KMP算法实现,VS2005平台语言C++,完全可以实现,我在主程序里加了一个for循环,为了测试时间,各位下了以后可以自行修改
用kmp算法实现在一个网页内网址的提取,自己实现kmp算法部分。
BF算法和Kmp算法实现串匹配完整代码。
KMP算法是数据结构中解决字符串匹配问题的经典算法,文件中包括算法实现和详细分析,下载可直接运行调试,可供数据结构与算法课程的学习
acm算法模板之kmp模板,对关键代码做了注释,帮助小白理解
高效的字符串匹配算法 KMP 实现,采用C语言实现
具体实现上,KMP算法使用一个next()函数,该函数包含模式串的局部匹配信息。在匹配失败时,next()函数用来确定模式串的最左可能有效匹配位置,而非简单地将模式串重新从左向右扫描。这样大大减少了不必要的匹配次数...
使用KMP算法实现一个模式匹配.doc
很多教材只是介绍了KMP的思想却没有实现,而他的实现对初学者又有一定难度,故共享该资源
模式匹配中的KMP算法的c语言实现及简单的应用介绍!