欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]
	}
}