1.2 字符串搜索

1.2.1 概述

字符串搜索也称为字符串匹配问题，在计算机工程中，除了匹配给定的模式子串外，还经常需要在一个巨大的文本主串中搜索子串、前缀、后缀和子序列。字符串搜索常见的算法有暴力搜索算法、KMP算法、BM算法、前缀树算法。

字符串搜索在搜索领域是一个经典问题。这个问题在安全、模式识别与文档匹配等领域有着广泛应用，比如，搜索引擎中的字符串自动补全功能。

搜索引擎是人类最智慧的发明之一。Google创始人佩奇曾经说过：终极的搜索引擎将像人类一样聪明。当用户输入一个字符时，搜索引擎将在1ms内返回数十个候选列表。当用户输入更多的字符时，会惊讶地发现它已经输出了自己想要搜索的主题或问题。这就是字符串搜索中的模糊匹配。

模糊匹配用来处理相似但不相同的查询，是一个非常有用的技术。搜索领域中经常使用模糊匹配功能来处理单词的拼写错误。但在很多时候，精确匹配还是最常用的搜索。

1.2.2 基础字符串搜索算法：暴力搜索算法

字符串搜索可以简化成：在文本主串M中查找模式子串P。

相比KMP与BM算法，暴力搜索不需要预先分析模式子串。通常来说，暴力搜索是最容易设计、实现和理解的算法。这也是为什么大多数初始情况下会使用暴力搜索尝试解决问题。暴力搜索的时间与空间成本与代价都特别高。在最坏的情况下，文本主串M和模式子串P的长度分别为m和p，对文本主串中每个字符进行p次比较，意味着搜索时间复杂度是O(m×p)。

通过一个实例来分析暴力搜索过程。假设文本主串M为"AFBEAG"，模式子串P为"BEAG"，在文本主串M中搜索模式子串P的过程如下。

● M[0] != P[0]，字符不匹配，文本主串索引i加1，模式子串索引j置0，即i=1，j=0。

AFBEAG
^
BEAG

● M[1] != P[0]，字符不匹配，文本主串索引i加1，模式子串索引j置0，即i=2，j=0。

AFBEAG
 ^
BEAG

● M[2] = P[0]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=1。

AFBEAG
  ^
BEAG

● M[3] = P[1]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=2。

AFBEAG
   ^
BEAG

● M[4] = P[2]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=3。

AFBEAG
    ^
BEAG

● M[5] = P[3]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=4。

AFBEAG
     ^
BEAG

● j=len(p)，在文本主串M中匹配到模式子串P。

暴力搜索算法的基本思想是：从文本主串第一个字符开始和模式子串的第一个字符进行比较，若相等，则继续比较；否则模式子串回溯到第一个字符，重新和文本主串的第二个字符进行比较。反复如此，直到文本主串结束。

代码清单1-1 暴力搜索算法的实现

type StringSearch struct {
   text            string
   pattern         string
   matchedPosition int
}
　
func NewStringSearch(pattern, text string) *StringSearch {
   return &StringSearch{
      text:            text,
      pattern:         pattern,
      matchedPosition: 0,
   }
}
　
func (ss *StringSearch) bruteForce() bool {
   n := len(ss.text)
   m := len(ss.pattern)
　
   for i := 0; i < n-m+1; i++ {
      j := 0
      for ; j < m; j++ {
         if ss.text[i+j] != ss.pattern[j] {
            break
         }
      }
　
      if j == m {
         ss.matchedPosition = i
         return true
      }
   }
   return false
}

暴力搜索算法是所有搜索算法设计策略中最简单、直观的方法。它可以解决广泛的实际问题，比如选择排序、冒泡排序、字符串搜索、深度优先搜索和广度优先搜索等。

任何时候都不要拒绝暴力搜索算法，而是要学会构建和改进它。面对新问题，开始时一定要找到一个暴力解决问题的方法。暴力解决方案让你真正理解问题，而不需要过多思考优化的解决方案，你将清楚知道问题的输入是什么，输出是什么，避免“见木不见林”的尴尬。暴力搜索算法给了你一个起点，你可以继续应用不同的技术来优化时间和空间复杂度。

1.2.3 中级字符串搜索算法：KMP算法

诚实地说，KMP算法是我见过最难学的算法之一，我花了不少时间才完全明白它是如何工作的。尽管它有些难度，但仍然值得你深入学习，当你掌握算法背后的思想后，你会忍不住在心里为它鼓掌。

如前所述，解决搜索问题最基本的方法是将文本主串M和模式子串P中的每个字符依次进行比较，每当出现错误匹配的时候，就将模式子串P整体向右移动一个位置，然后重复之前的比较逻辑。很明显，它的时间复杂度是O(m×p)，其中m和p分别是文本主串和模式子串的长度。有没有更好的优化算法呢？当然有。KMP算法通过预先分析模式子串，并且尝试重用模式子串初始部分中已经匹配的内容，以避免重新匹配。

分析实例之前，需要理解两个概念：前缀与后缀。前缀表示除了最后一个字符以外，一个字符串的全部头部组合；后缀表示除了第一个字符以外，一个字符串的全部尾部组合。以"BABAB"为例，对前缀和后缀的解释如下。

● "B"的前缀和后缀都为空集，共有元素的长度为0。

● "BA"的前缀为[B]，后缀为[A]，共有元素的长度为0。

● "BAB"的前缀为[B, BA]，后缀为[AB, B]，共有元素的长度为1。

● "BABA"的前缀为[B, BA, BAB]，后缀为[ABA, BA, A]，共有元素的长度为2。

● "BABAB"的前缀为[B, BA, BAB,BABA]，后缀为[ABAB, BAB, AB,B]，共有元素的长度为3。

图1-1中展示了一种情况，其中文本主串和模式子串在索引为3的位置出现了不一致。默认情况下，下一步应该将模式子串P向右移动一个位置。由于模式子串P中每个字符都是不同的，可以简单判断出模式子串P[0..2]区间（即以索引0起始，以索引2结尾的连续数组）内的字符都不可能与文本主串M当前的字母E匹配，将模式子串向右移动一个位置是徒劳的，所以需要将模式子串向右移动其自身长度减1个位置，让模式子串P的首个字符与文本主串M当前的字母E进行匹配。

图1-1

图1-2展示了另一种情况，文本主串和模式子串在索引为5的位置出现了不一致。当字母不匹配的时候，究竟要将模式子串P移动多少个位置才是合适且高效的？通过观察，模式子串前缀子串P[0,1]="DE"与模式子串后缀子串P[3,4]= "DE"是完全相同的。实际上，P[0,4]构成的子串中，存在一个前缀"DE"与后缀"DE"是完全相同的，这种情况下应该将模式子串移动到文本主串索引为3的位置继续比较。

图1-2

为了一般化地表达这个问题，假设pSub1=pSub2且pSub2=mSub3，当pSub2的下一个字符和mSub3的下一个字符不匹配时，可以移动模式子串让pSub和mSub3对齐，比较pSub1的下一个字符是否和mSub3的下一个字符匹配。图1-3展示了当文本主串与模式子串失配时，下一步应该从哪个位置开始继续进行字符的比较。这么做的好处是：文本主串的遍历索引i不用回溯，模式子串的遍历索引 j可能需要回溯，但并不一定每次都需要将索引j回溯到索引0。

现在你肯定明白了，如果可以提前找出模式子串的每个前缀，算法就可以跳过一些不必要的匹配，极大提高工作效率。这实际上也就是KMP算法背后的核心思想。

图1-3

下面说明如何寻找前后缀单元格。

如前所述，暴力搜索算法在遇到模式子串P与文本主串M不匹配的情况时，简单地将模式子串P向右移动一个位置并继续比较。KMP算法中引入了一个Next[]数组，Next[]中的值决定下一个要比较的字符的位置。

当M[i] != P[j]时，将模式子串P的失配位置j看成一个字符串的终点，若该字符串的前缀与后缀相等，即P[0..k-1] == P[j-k..j-1]，那么继续将P[k]位置的字符与M[i]位置的字符进行比较。令Next[j]=k，表示当P[j] != M[i]，即模式子串P的j位置发生失配时，模式子串的遍历索引j应该回溯到位置k。

上面的表达比较抽象，怎么直观理解Next[j]=k公式中j与k的对应关系呢？以索引j为终点（不包含索引j本身）的模式子串P[0..j-1]中，后缀与前缀的最长匹配长度是k。如图1-4所示，其中P[0..k-1] = P[j-k..j-1]。

图1-4

Next[j]=k包含如下3层含义，可结合图1-5理解。

● 当P[j] != M[i]时，模式子串的遍历索引j应该回溯到位置k。

● Next[j]的值等于P[0..i]的最长前缀的长度，也等于P[0..i]的最长后缀的长度。

● k的值等于P[0..i]的最长前缀的长度，也等于P[0..i]的最长后缀的长度。

图1-5

如图1-5所示，Next[j]=k是KMP算法的关键，其背后思想是，模式子串P在索引j-1处与文本主串M匹配，但是在索引j处失配。根据Next[j]=k，我们知道模式子串P的最长前缀（同时也是P的最长后缀）的长度为k。因此，我们已经知道：

● P[0..j-1]与M[i-j..i-1]完全匹配，P[j]与M[i]失配，即P[0..j-1]=M[i-j..i-1]；

● Next[j]=k，即P[0..k-1]与P[j-k..j-1]是完全匹配的，即P[0..k-1]=P[j-k..j-1]。

根据等式的传递性可推导出：P[0..Next[j]-1]=M[i-Next[j]..i-1]，即模式子串区间P[0..Next[j]-1]与文本主串区间M[i-Next[j]..i-1]是完全匹配的。

所以，P[j]与M[i]失配后，保持文本主串索引i不变，而模式子串索引j回溯到索引Next[j]，恢复匹配过程。

下面通过一个实例来分析Next[]数组是如何初始化的，如图1-6所示。

图1-6

● 当j=0时，模式子串P[0..j-1]=P[0..-1]是一个无效区间，因此将Next[0]设置为−1。

● 当j=1时，模式子串P[0..j-1]=P[0..0]是一个单个字母"B"，根据前后缀定义，单个字母没有前后缀，因此将Next[1]设置为0。

● 当j=2时，模式子串P[0..j-1]=P[0..1]包含两个字母"BA"，"BA"没有相同的前后缀，因此将Next[2]设置为0。

● 当j=3时，模式子串P[0..j-1]=P[0..2]包含3个字母"BAB"，"BAB"有一个相同的前后缀串，即"B"，因此将Next[3]设置为1。

● 当j=4时，模式子串P[0..j-1]=P[0..3]包含4个字母"BABA"，"BABA"有一个相同的前后缀串，即"BA"，因此将Next[4]设置为2。

● 当j=5时，模式子串P[0..j-1]=P[0..4]包含5个字母"BABAB"，"BABAB"有一个相同的前后缀串，即"BAB"，因此将Next[5]设置为3。

● 当j=6时，模式子串P[0..j-1]=P[0..5]包含6个字母"BABABB"，"BABABB"有一个相同的前后缀串，即"B"，因此将Next[6]设置为1，如图1-7所示。

图1-7

将上述分析过程转成以下代码，主要对模式子串进行预处理从而初始化next[]数组。

代码清单1-2 初始化next[]数组

func (ss *StringSearch) buildNext() []int {
   next := make([]int, len(ss.pattern))
   next[0], next[1] = -1, 0
　
   matchCnt := 0
   for idx := 2; idx < len(ss.pattern); {
      // check prefix and suffix
      if ss.pattern[idx-1] == ss.pattern[matchCnt] {
         matchCnt++
         next[idx] = matchCnt
         idx++
      } else if ss.pattern[idx-1] != ss.pattern[matchCnt] && matchCnt != 0 {
         matchCnt = next[matchCnt]
      } else {
         next[idx] = 0
         idx++
      }
   }
　
   return next
}

我们知道，暴力搜索算法的时间复杂度是O(m×p)，其中m和p分别是文本主串和模式子串的长度。使用KMP算法在文本主串M中搜索模式子串P时，比较两个字符串，当字符比较发生失配时，模式子串中包含足够多的信息来确定下一个匹配的位置，从而减少回溯来提升字符串搜索算法的效率。KMP算法的时间复杂度是O(m+p)。因为文本主串M没有回溯，基于next[]数组信息，模式子串P也几乎没有回溯。

代码清单1-3 KMP算法的实现

func (ss *StringSearch) kmp() bool {
   next := ss.buildNext()
   // i - current char in text; j - current char in pattern
   i, j := 0, 0
   for i < len(ss.text) {
      if ss.text[i] != ss.pattern[j] {
         if j == 0 {
            i++
         } else {
            j = next[j]
            //j = next[j - 1]
         }
      } else {
         i++
         j++
         if j == len(ss.pattern) {
            fmt.Printf("%s found the pattern(%s) at :%d", ss.text, ss.pattern, i-j)
            ss.matchedPosition = i - j
            return true
         }
      }
   }
　
   return false
　
}

1.2.4 高级字符串搜索算法：BM算法

KMP算法虽然广为人知，但它在实践中远不如BM算法。与前面介绍的暴力搜索算法时间复杂度O(m×p)不同，KMP与BM算法只需要线性时间就能在文本主串中找到模式子串。KMP与BM算法都需要对模式子串提前进行预处理，以便在比较字符过程中跳过字符，避免无效回溯。KMP算法的预处理规则是对模式子串的每个位置计算最长前缀和最长后缀的长度。

BM算法与KMP算法的不同之处在于，它从右到左进行字符串的比较，并且使用不同的预处理规则，即坏字符规则，如图1-8所示。

图1-8

如图1-8所示，从模式子串末尾向前匹配时，如果发现某个字符失配，则称这个失配的字符为坏字符。注意，坏字符指的是文本主串中的字符，并不是模式子串中的字符。

图1-9中，当假定文本主串中的坏字符与模式子串中索引为j的字符失配时：

● 如果文本主串中的坏字符在模式子串中存在，则把坏字符在模式子串中的索引记为k；

● 如果文本主串中的坏字符在模式子串中不存在，则把坏字符在模式子串中的索引k记为−1。

那么，当文本主串M与模式子串P不匹配时，模式子串需要向左移动的距离是j−k。

图1-9

通过一个实例来分析BM算法，其中文本主串M为"ADAYZABC"，模式子串P为"ABC"。首先初始化slideTable表格，即坏字符表格，如图1-10所示。

图1-10

● 当i=0，j=2时，M[0+2]与P[2]失配，坏字符'A'在模式子串中的索引k=0。根据公式j−k，将模式子串向左移动两个位置，等价于将文本主串索引i向右移动两个位置，即文本主串下一次比较索引i=2的位置。

ADAYZABC
  ^
ABC

● 当i=2，j=2时，M[2+2]与P[2]失配，坏字符'Z'在模式子串中的索引k=−1。根据公式j−k，将模式子串向左移动3个位置，等价于将文本主串索引i向右移动3个位置，即文本主串下一次比较索引i=5的位置。

ADAYZABC
    ^
ABC

● 当i=5，j=2时，M[5+2] = P[2]，模式主串和模式子串中的字符'C'匹配。

ADAYZABC
       ^
ABC

● 当i=5，j=1时，M[5+1] = P[1]，模式主串和模式子串中的字符'B'匹配。

ADAYZABC
      ^
ABC

● 当i=5，j=0时，M[5+0] = P[0]，模式主串和模式子串中的字符'A'匹配。

ADAYZABC
     ^
ABC

● 当j=−1时，说明在文本主串中找到了模式子串，其从文本主串的索引i=5处开始匹配。

代码清单1-4 初始化坏字符表格

func (ss *StringSearch) buildSlideTable() [256]int {
   var st [256]int
   for idx := 0; idx < 256; idx++ {
      st[idx] = -1
   }
　
   for idx := 0; idx < len(ss.pattern); idx++ {
      st[ss.pattern[idx]] = idx
   }
　
   return st
}

回顾暴力搜索算法、KMP算法与BM算法，后两者在搜索匹配模式时，不会遍历整个搜索空间，而是基于预先分析的模式子串的信息，智能地跳过文本中一些无用的搜索空间，从而有效减少每次搜索中必须进行比较的字符数量。

代码清单1-5 BM算法的实现

func (ss *StringSearch) BM() bool {
   st := ss.buildSlideTable()
   textLen := len(ss.text)
   patternLen := len(ss.pattern)
　
   // Leon Bug
   //for idx := 0; idx < textLen-patternLen; idx++ {
   for idx := 0; idx < textLen-patternLen+1; {
　
      j := patternLen - 1
      //iterate pattern string from end to beginning
      for ; j >= 0; j-- {
         if ss.pattern[j] != ss.text[idx+j] {
            break
         }
      }
　
      if j < 0 {
         fmt.Printf("found pattern")
         ss.matchedPosition = idx
         return true
      }
　
      //Pattern string slides backward:
      idx = idx + (j - st[ss.text[idx+j]])
   }
　
   return false
}

1.2.5 字符串精确搜索：Grep

前面介绍了3种搜索算法，现在介绍搜索算法的具体应用。

Grep是一个文本搜索工具，它支持使用正则表达式搜索文件，并将匹配的行输出。Grep强大的文本搜索能力，得益于它使用的BM算法。BM算法首先查找模式子串的最后一个字符，然后使用一个查找表来告诉Grep，当发现一个失配字符时，它可以在后续匹配比较中跳过一些字符。因此，如果可以确保模式子串中最后一个字符是实际字符，而不是范围或者通配符，就可以显著加快搜索速度。

在Linux中，经常需要在一个或者多个文件中进行搜索。下面通过几个例子来介绍Linux中Find与Grep工具的基本用法。

● 使用Find在多个文件中搜索。

 find ./ -type f -name '*.md'

● 使用Grep显示/etc/passwd 文件中不包含字符串 "nologin" 的行。

 grep -v nologin /etc/passwd

● 使用Grep在当前目录中的所有文件中搜索字符串"MySQL"。

 grep -rn MySQL  ./

● 使用Grep搜索 Nginx 日志错误文件中的多个字符串。

grep 'fatal\|error\|critical' /var/log/nginx/error.log

那么Find与Grep这两个工具有什么区别呢？

Grep工具基于正则表达式从文件或者数据流中匹配数据，而Find工具根据文件的元数据来选择文件，元数据包含文件名的大小、时间和类型。简单来说，Grep用来搜索文件的内容，而Find用来搜索文件系统。对于每个匹配Find输出的文件，打开每个文件并使用 Grep 搜索模式。下面是通过管道（Pipeline）将Find与Grep工具组合使用的示例：

find /var/log/nginx/ -type f -name '*.log' |  grep -E 'fatal|error|critical'

1.2.6 字符串模糊搜索

当你在搜索引擎中进行搜索的时候，可能你想搜索的内容还没有输入完整，搜索引擎就猜出你想要搜索的内容了，比如，当用户输入“Google”后搜索引擎会返回如图1-11所示的候选内容列表，这就是字符串模糊搜索功能。

图1-11

实现字符串模糊搜索功能需要两项技术，一个是字符串自动补全，用于根据已有关键词查找所有相关的问题；另一个是字符串相似度，用于计算这些相关问题中哪个更可能是用户想要搜索的。

1．字符串自动补全：Trie树

你可能会疑惑，搜索引擎自动补全的这些问题或者建议究竟来自哪里？数据是以怎样的数据结构组织的？自动补全功能是基于前缀树（Trie Tree，又称字典树、单词查找树）数据结构实现的，根据字符串前缀预测用户正在输入的单词的剩余部分。搜索引擎的自动补全功能将用户的输入作为前缀。Trie树的数据结构主要用于以检索为目标的字符串处理和存储。图1-12说明了具体情形。

图1-12

相比于普通的二叉树，Trie树中每个节点至多有26个子节点，这些子节点分别对应26个字母（a～z）。这是一种时间效率很高的数据结构，用于存储和检索字符串。比如，用户的历史查询内容以Trie树的数据结构进行组织和存储，以便搜索。然而，Trie树有一个明显的缺点，即占用大量的内存，因为每个节点都包含一个长度为26的字符数组，用来存储所有子节点，以便对Trie树进行插入、检索和删除操作。

向Trie树中插入内容时，从根节点向下遍历到叶子节点。如图1-13所示，观察"CAT"与"CAP"两个输入单词，它们有共同前缀"CA"，则该前缀只需要在Trie树中存储一次，因此极大地降低了Trie树的空间开销。而对于一些经典的数据结构，比如链表（List），它将每个单词存储在一个单独元素空间，并不会将单独元素空间关联起来。换句话说，这些单词中所有的共同前缀都被重复存储在独立的元素空间中。相比而言，Trie树的存储空间成本更低。

图1-13

对Trie树进行检索的过程是从根节点出发，对于想要检索的内容从左到右枚举每个字母，检查当前节点是否有与该字母对应的子节点。如果没有对应的子节点，则表示检索失败，返回false。如果有对应的子节点，则重复上述步骤，直到分析完想要检索的全部内容。

使用深度优先搜索（Depth First Search，DFS）遍历Trie树结构时，可以收集用户输入的字符前缀的所有字符候选集。当我们讨论在数据结构中进行数据检索的时候，通常会想到哈希表（Hash Table）。哈希表非常高效，但Trie树的数据结构还是有独特优势的。比如，哈希表需要定义哈希函数，无法避免哈希冲突。

对Trie树执行插入操作时，当前节点的后继节点对应哪个子节点指针，就应该使用Children[]数组中的哪一个位置。此处采用idx = int(chr - 'a')逻辑来计算Children[]数组对应的索引位置。

代码清单1-6 Trie树的算法实现

package trie
　
type Trie struct {
   root *TrieNode
}
　
type TrieNode struct {
   Keyword  string
   Children [26]*TrieNode
}
　
func NewTrieNode() *TrieNode {
   return &TrieNode{
      Keyword:  "",
      Children: [26]*TrieNode{},
   }
}
func NewTrie() *Trie {
   return &Trie{
      root: NewTrieNode(),
   }
}
　
func (t *Trie) Insert(word string) {
   cur, idx := t.root, -1
   for _, chr := range word {
      idx = int(chr - 'a')
      if cur.Children[idx] == nil {
         cur.Children[idx] = NewTrieNode()
      }
      cur = cur.Children[idx]
   }
   cur.Keyword = word
}
　
func (t *Trie) Inserts(words ...string) {
   for _, word := range words {
      t.Insert(word)
   }
}
　
func (t *Trie) Removes(words ...string) {
   for _, word := range words {
      t.Remove(word)
   }
}
　
func (t *Trie) Remove(word string) {
   cur, stack := t.root, make([]*TrieNode, 0, len(word))
   for _, chr := range word {
      stack = append(stack, cur)
      cur = cur.Children[int(chr-'a')]
      if cur == nil {
         return
      }
   }
　
// check whether cur node is leaf or not
   if !t.IsLeaf(cur) {
      return
   }
　
   //iteration: from bottom to up
   for idx := len(word) - 1; idx >= 0; idx-- {
      cur, stack = stack[len(stack)-1], stack[:len(stack)-1]
　
      j := int(word[idx] - 'a')
      cur.Children[j] = nil //delete it
　
      //important: trigger delete from bottom to up only when current node is becoming leaf
      if !t.IsLeaf(cur) {
         return
      }
　
      cur.Keyword = ""
   }
}
　
// check whether cur node is leaf or not
func (t *Trie) IsLeaf(node *TrieNode) bool {
   for _, child := range node.Children {
      if child != nil {
         return false
      }
   }
   return true
}
　
func (t *Trie) FindWord(word string) bool {
   cur := t.root
   for _, chr := range word {
      idx := int(chr - 'a')
      cur = cur.Children[idx]
      if cur == nil {
         return false
      }
   }
　
   if cur.Keyword != word {
      return false
   }
   return true
}

2．字符串相似度：编辑距离算法

搜索引擎如何判断用户更希望输入哪个单词呢？它需要比较用户输入的单词与单词历史库中的哪个单词的编辑距离（Edit Distance，又称莱文斯坦距离，Levenshtein Distance）最小，并基于上下文来推断用户希望输入的单词。

如果要构建一个简单的拼写检查器或者进行字符串相似度判断，使用编辑距离算法就足够了。两个字符串之间的编辑距离是指将一个字符串更改为另一个字符串所最少需要的编辑单个字符的次数。编辑单个字符的次数越少，两个字符串之间的相似度就越高。所谓编辑单个字符，是指对一个字符串添加一个字母、删除一个现有字母，或用其他字母替换一个现有字母。举例如下。

kitten与sitting的编辑距离为3：
　
kitten -> sitten (字母s替代k)
sitten -> sittin (字母i替代e)
sittin -> sitting (末尾添加字母g)

将求解的问题转换成子问题的过程称为“状态转移”，而状态转移的表达式进一步称为状态转移方程式。为了方便理解，可以将状态转移方程式理解为递归关系。

通过一个实例来分析计算编辑距离的算法过程：有两个字符串"KITTEN" 与"SITTING"，获得两个字符串之间的编辑距离。两个字符串之间的删除、替换和插入等操作次数的值可以在表或者矩阵中进行表示。

矩阵的第一行和第一列分别由两个字符串的每个字符的值填充，两个完整字符串之间的编辑距离由矩阵右下角的值表示。矩阵中第i行j列的值，即vector[i] [j]，表示将第一列中前i个字符组成的字符串转换为第一列中前j个字符组成的字符串所需要执行的操作次数。比如，将一个空字符串变成"K"需要插入一个字母"K"，所以vector[0] [1]=1；将一个空字符串变成"KI"需要插入包含两个字母的序列"KI"，所以vector[0] [2]=2；将一个空字符串变成"KITTEN"需要插入包含6个字母的序列"KITTEN"，所以vector[0] [6]=6。其他依此类推，如图1-14所示，其中dis[i] [j] 表示str1[0..i]和str2[0..j]两个字符串的最小编辑距离。

图1-14

分析dis[1] [1]的值，即"S"字符串与"K"字符串之间的编辑距离是多少？只需要将"S"经过一次替换操作变成"K"，这样两个字符串就相同了，所以dis[1] [1]=1。

分析dis[1] [2]的值，即"S"字符串与"KI"字符串之间的编辑距离是多少？只需要将"S"经过一次替换操作变成"K"并插入一个新字符"I"，这样两个字符串就相同了，所以dis[1] [2]=2。其他依此类推，如图1-15所示。

图1-15

继续分析下一行，分析dis[2] [1]的值，即"SI"字符串与"K"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，并追加一次删除操作，将其变成"K"，这样两个字符串就相同了，所以dis[2] [1]=2。

分析dis[2] [2]的值，即"SI"字符串与"KI"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，这样两个字符串就相同了，所以dis[2] [2]=1。

分析dis[2] [3]的值，即"SI"字符串与"KIT"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，并追加一次插入操作将其变成"KIT"，这样两个字符串就相同了，所以dis[2] [3]=2，如图1-16所示。

图1-16

至此，有两个关键信息需要说明。

● 当计算dis[2] [2]的值时，"SI"与"KI"字符串的末尾两个字符相同，此时dis [2] [2]的值与其左上角dis [1] [1]的值相同。

● 当计算dis[2] [3]的值时，"SI"与"KIT"字符串的末尾两个字符不相同，此时dis [2] [3]的值是周围3个值中的最小值加1，如图1-17所示。

图1-17

因为dis[i] [j] 表示str1[0..i]和str2[0..j] 两个字符串的最小编辑距离，所以dis[i] [j]的状态只与附近的3个状态dis[i] [j-1]（通过插入操作可到达dis[i] [j]）、dis[i-1] [j]（通过删除操作可到达dis[i] [j]）和dis[i-1] [j-1]（通过替换操作可到达dis[i] [j]）有直接关系。代码如下：

dis(i,j) = min(
           dis(i, j-1) + 1,
//for insertion operation
           dis(i-1, j) + 1,
//for deletion operation
           dis(i-1, j-1) + (str1[i] == str2[j] ? 0 : 1)   
//for subtitution operation
)

下面展示计算编辑距离的完整算法实现。

代码清单1-7 计算编辑距离的算法实现

func Distance(str1, str2 string) int {
   dp := make2DArray(len(str1)+1, len(str2)+1)
　
   for idx := 0; idx <= len(str1); idx++ {
      dp[idx][0] = idx
   }
　
   for idx := 0; idx <= len(str2); idx++ {
      dp[0][idx] = idx
   }
　
   for row := 1; row <= len(str1); row++ {
      for column := 1; column <= len(str2); column++ {
         if str1[row-1] == str2[column-1] {
            dp[row][column] = dp[row-1][column-1]
         } else {
            dp[row][column] = min(dp[row-1][column], dp[row][column-1], dp[row-1] column-1]) + 1
         }
      }
   }
　
   return dp[len(str1)][len(str2)]
}
　
func min(values ...int) int {
   if len(values) <= 0 {
      return -1
   }
　
   var minVal int
   minVal, values = values[0], values[1:]
   for _, val := range values {
      if val < minVal {
         minVal = val
      }
   }
　
   return minVal
}
　
func make2DArray(rows, columns int) [][]int {
   matrix := make([][]int, rows)
　
   for idx := range matrix {
      matrix[idx] = make([]int, columns)
   }
　
   return matrix
}