P19 字符串搜索(BF，RK，BM，KMP)

红太狼 2022-09-03 01:18 108阅读 0赞

# 一、BF #

func BF(ss, sub string) (index int) { 
    	for i, j := 0, 0; i < len(ss); i++ { 
    		if ss[i] == sub[j] {  // 相等，同时后移
    			j++
    		} else {  // 不相等, 重新匹配
    			j = 0
    		}
    		if j == len(sub) {  // 匹配完
    			return i - j + 1
    		}
    	}
    	return -1
    }
    func main(){ 
    	var ss string = "ABCABABABCABCD"
    	var sub string = "BCABC"
    	fmt.Println(BF(ss, sub))
    }

# 二、RK #

func md5sum(s string) string { 
    	h := md5.New()
    	io.WriteString(h, s)
    	return fmt.Sprintf("%x", h.Sum(nil))
    }
    func RK(ss, sub string) (index int) { 
    	subMD5 := md5sum(sub)
    	for i := 0; i <= len(ss)-len(sub); i++ { 
    		item := ss[i : i+len(sub)]
    		itemMD5 := md5sum(item)
    		if itemMD5 == subMD5 { 
    			return i
    		}
    	}
    	return -1
    }
    func main() { 
    	var ss string = "ABCABABABCABCD"
    	var sub string = "BCAGBC"
    	fmt.Println(RK(ss, sub))
    }

# 三、BM #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]

func BM(ss, sub string) (index int) {  // BBBAC ->AC
    	var length = len(sub)
    	var i, j = length - 1, length - 1
    	var step, broken = 0, false
    	for i <= len(ss) {  // 3-2
    		if ss[i] != sub[j] {  // 没对上, j前移
    			j--
    			step++
    			broken = true
    		} else {  // 对上了,匹配上一对
    			i--
    			j--
    		}
    		if j == -1 {  // 子串匹配完
    			if !broken {  //连续未中断
    				return step
    			} // i跳过未匹配上的个数, j重置
    			j = length - 1
    			i = j + step
    			broken = false
    		}
    	}
    	return -1
    }

# 四、KMP #

前菜：

*  S为字符串。若X+Y=S；X、Y不为None，X为S的前缀，Y为S的后缀

左边为寻找Next数组，该数组的作用是下一步取子串的几号位跟当前未匹配上的父字符进行比较  
右边是根据Next数组，实现子串查找代码逻辑  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 4]  
所以先当我们已经知道子串ABABAAABABAA的Next数组为\[-1,0,0,1,2,3,1,1,2,3,4,5\]  
现在来用右边的代码片段拼凑KMP算法

func kmp(str, sub []string, next []int) (index int) { 
    	for i, j := 0, 0; i < len(str); { 
    		fmt.Println(i, j)
    		if str[i] == sub[j] {  // 两字符相同，同时后移
    			i++
    			j++
    		} else {  // 两字符不相同
    			n := next[j]
    			if n < 0 {  // 让当前父串的位置对子串的-1位(nil)，相当于父串的下一位对子串的0位
    				fmt.Printf("取子串的第%d位(nil) 与 父串的第%d位(%s) 相比; ", n, i, str[i])
    				i++
    				j = 0
    				fmt.Printf("等同于让父串的位置+1(%d位) 与 子串第0位相比\n", i)
    			} else {  // 取第几位与父串当前位比
    				j = n
    				fmt.Printf("取子串的第%d位(%s) 与 父串的第%d位(%s) 相比\n", j, sub[j], i, str[i])
    			}
    		}
    		if j == len(sub) {  // 如果下一位已经到末尾则匹配完毕
    			return i - len(sub)
    		}
    	}
    	return -1
    }
    
    func main() { 
    	// 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 22
    	// * * * * * * * * x
    	str := "A B A B A A A B A B C A B A B A A A B A B A A"
    	sub := "A B A B A A A B A B A A"
    	next := []int{ -1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5}
    	index := kmp(strings.Fields(str), strings.Fields(sub), next)
    	fmt.Println(index)
    }

## 4.1 求Next数组 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 5]  
举个例子next\[9\]=3是怎么算出来的？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 6]  
代码实现

func getNext(sub []string) []int { 
    	result := make([]int, 2, len(sub))
    	result[0] = -1                           // 下一步就是拿index为-1的子串对准当前父串的字符
    	result[1] = 0                            // 1位字符没有前后缀
    	getMaxSuffix := func(arr []string) int {  // 获取最长前后缀
    		var i, j = 1, 0
    		var hit int // 连续命中个数
    		for in := i; i < len(arr); { 
    			if arr[i] == arr[j] { 
    				i++
    				j++
    				hit++
    			} else { 
    				hit = 0 // 连续匹配中断了, 清空
    				in++    // 定位到父串下一个
    				i = in  // 重置，从父串下一个开始
    				j = 0   // 子串从0开始匹配父串下一个
    			}
    		}
    		return hit
    	}
    	for i := 2; i < len(sub); i++ { 
    		result = append(result, getMaxSuffix(sub[:i]))
    	}
    	return result
    }
    func main() { 
    	sub := "A B A B A A A B A B A A"
    	fmt.Println(getNext(strings.Fields(sub)))
    }

> \[-1 0 0 1 2 3 1 1 2 3 4 5\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70]: /images/20220829/de2af08dbeba4436a3aef1ecd09383b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 1]: /images/20220829/e7f2cc20d43d4ca9a75bf15be7d1066f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 2]: /images/20220829/1fab8b0c9a8245f99dd6d354a887a9d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 3]: /images/20220829/0c0ec031c2f449cea8a52426e3937269.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 4]: /images/20220829/139df7440aa34b58adeafe277e74b1d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 5]: /images/20220829/a049804b568843b38e12782ddb181aaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70 6]: /images/20220829/8955fd23d2c645caa9f5963a7d2a7d58.png