Golang实现的KMP字符串匹配算法
发布时间:2020-12-16 18:54:42 所属栏目:大数据 来源:网络整理
导读:算法的细节可以参考网上的资料或数据结构的相关教材,这里直接上代码了~ 鉴于本人技艺浅陋,有的地方写的可能不合理,代码略长,如果有改进之处,请留言指点,算法本身测试过了: package mainimport ("fmt")func GetNextValueArray(sub []byte) (next []int
算法的细节可以参考网上的资料或数据结构的相关教材,这里直接上代码了~ 鉴于本人技艺浅陋,有的地方写的可能不合理,代码略长,如果有改进之处,请留言指点,算法本身测试过了: package main import ( "fmt" ) func GetNextValueArray(sub []byte) (next []int) { var ( length int = len(sub) middle int compare_left int compare_right int match_count int ) next = make([]int,length) next[0] = 0 next[1] = 0 for i := 2; i < length; i++ { middle = i / 2 match_count = 0 if i%2 == 0 { for j := 0; j < middle; j++ { compare_left = 0 compare_right = i - 1 - j for compare_left <= j { if sub[compare_left] != sub[compare_right] { break } compare_left++ compare_right++ } if compare_left == j+1 { match_count++ } } next[i] = match_count } else { for j := 0; j <= middle; j++ { compare_left = 0 compare_right = i - 1 - j for compare_left <= j { if sub[compare_left] != sub[compare_right] { break } compare_left++ compare_right++ } if compare_left == j+1 { match_count++ } } next[i] = match_count } } return next } func ReviseNextValueArray(next []int) []int { var length int = len(next) for i := 2; i < length; i++ { if next[i] == next[next[i]] { next[i] = next[next[i]] } } return next } //在content中的start-end之间寻找sub子串 //成功返回匹配成功的起始下标,匹配失败则返回-1 func KMP(content []byte,start_index int,end_index int,sub []byte) (index int) { var ( next []int = ReviseNextValueArray(GetNextValueArray(sub)) sub_index int = 0 sub_length int = len(sub) ) for i := start_index; i <= end_index; i++ { if content[i] == sub[sub_index] { match_start := i for j := sub_index; j <= sub_length; j++ { if j == sub_length { return match_start - sub_index } if i >= end_index || content[i] != sub[j] { sub_index = next[j] break } i++ } } } return -1 } func main() { content := []byte("why every programming language use the hello world as the first test???") sub := []byte("hello world") fmt.Println(KMP(content,len(content)-1,sub)) }
如果转载请注明出处:http://blog.csdn.net/gophers/article/details/23128345 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |