kmp算法实现
程序员文章站
2022-06-05 23:22:18
...
工作一直做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算法实现
推荐阅读
-
Asp.net MVC3实现JSONP
-
纯 js 实现上传文件支持拖拽
-
判断php数组是否为索引数组的实现方法_PHP教程
-
Python实现信息轰炸工具(再也不怕说不过别人了)
-
jQuery截取指定长度字符串的实现原理及代码_jquery
-
Javascript获取CSS伪元素属性的实现代码_javascript技巧
-
MySQL 多表查询实现分析
-
编写一个函数reverse_string(char * string)(递归实现)实现:将参数字符串中的字符反向排列。 要求:不能使用C函数库中的字符串操作函数
-
jQuery通过控制节点实现仅在前台通过get方法完成参数传递_jquery
-
一个PHP算法,php数组一个二维数组拆分成多个子数组