简介

字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为模式串）。在 Golang 中，可以使用最常见的字符串匹配算法之一：Knuth-Morris-Pratt（KMP）算法，它的时间复杂度为 O(n+m)，其中 n 和 m 分别为文本串和模式串的长度。

KMP实现代码

mermaid解说图
在这里插入图片描述

package mainimport "fmt"// KMP 算法用于在一个文本串中查找一个模式串
// 其中，text 为文本串，pattern 为模式串
// 返回值为模式串在文本串中第一次出现的位置，如果未找到，则返回 -1
func kmp(text, pattern string) int {n, m := len(text), len(pattern)if m == 0 {return 0}if n < m {return -1}// 构建前缀表（partial match table）pmt := make([]int, m)for i, j := 1, 0; i < m; i++ {// 寻找最长公共前后缀的长度for j > 0 && pattern[i] != pattern[j] {j = pmt[j-1]}if pattern[i] == pattern[j] {j++}pmt[i] = j}// 在文本串中匹配模式串for i, j := 0, 0; i < n; i++ {// 如果匹配不成功，利用前缀表来找到一个新的匹配位置for j > 0 && text[i] != pattern[j] {j = pmt[j-1]}// 如果匹配成功，则继续匹配下一个字符if text[i] == pattern[j] {j++}// 如果匹配成功，返回模式串在文本串中第一次出现的位置if j == m {return i - m + 1}}// 如果未找到，则返回 -1return -1
}func main() {var num = kmp("韩实施一个如何使得覅上的换个地方韩浩", "韩浩")fmt.Println(num)
}