实现常用数据结构(串)

定义

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统 (如搜索引擎)、文本编辑程序(如 Word)、问答系统、自然语言翻译系统等，都是以字符串数据作为处理对象的。

串的存储表示

1. 定长顺序存储 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。
2. 堆分配存储 堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。
3. 块链存储 类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性 (每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

KMP 算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这三人的姓氏命名此算法。

下面先直接给出 KMP 的算法流程：

• 假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
  • 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
  • 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
    • 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值（next 数组的求解会在下文的 3.3.3 节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于 1。

很快，你也会意识到 next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如，如果 next [j] = k，代表 j 之前的字符串中有最大长度为 k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到 next [j] 的位置）。如果 next [j] 等于 0 或 -1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符，而不是跳到开头，且具体跳过了 k 个字符。

转换成代码表示，则是：

func getNextList(str string) []int {
 next := make([]int, len(str))
 next[0] = -1
 i, j := 0, -1
 for i < len(str)-1 {
  if j == -1 || str[i] == str[j] {
   j++
   i++
   next[i] = j
  } else {
   j = next[j]
  }
 }
 return next
}

func KMP(str, target string) int {
 next := getNextList(target)
 i, j := 0, 0
 for i < len(str) && j < len(target) {
  if str[i] == target[j] || next[j] == -1 {
   i++
   j++
  } else {
   j = next[j]
  }
 }
 if j == len(target) {
  return i - len(target)
 }
 return -1
}