回顾
上一节我们学习了两种低效的排序算法，这次我们来看看一个关于搜索的问题：字符串匹配（string matching）。在算法的问题类型那一节里面我们提到了这个问题，这好比你在浏览网页或者在看电子书的时候按下“Ctrl+F”键，然后你输入一个单词或一段话，算法就在原文中自动帮你找到那些匹配的文字。
上图截自《算法导论》的某一页，我在我自己的电脑里试了一下，搜索的是单词“algorithm”，几秒钟就全部搜出来了，可以说速度还是非常快的，要知道这本书可是有 1000 多页的呀，这得益于一种高效的算法帮我们能够在短时间内完成复杂的工作，本节内容只学习如何暴力法来求解。
这类问题看似很简单，但这也是困扰了科学家们多年，直到现在对搜索算法的研究都还没有停止，因为解决这个问题并不难，我们只需要用最简单粗暴的办法就可以解决掉它，但要找到一种高效的算法却是难上加难。我会在后面的内容中介绍一种更高效的算法。
一个例子
这里我们举一个更加有意思的例子。懂一点生物的小伙伴们肯定知道，DNA 探针（一段短的单链 DNA 序列）在与一段长的 DNA 分子杂交的时候，它们的碱基一定会遵循配对原则，即：A 跟 T 配对，C 跟 G 配对。那么 DNA 探针如何从 DNA 分子中找到与自己互补的序列呢？其实我们完全可以抽象成一个字符串匹配问题。首先，我们把被配对的 DNA 分子对应的碱基序列叫做主串，英文叫plain text，而用于配对的探针 DNA 序列则叫做模式串（patten string）。
暴力求解的方式很简单，从原串的起始位置开始，与模式串的第一个字符对齐，进行比对。如果比对成功，就比较模式串和原串下一个字符，如果全部比对成功，则返回比对成功的对应的索引；如果比对失败，模式串就整体向右移动一个单位，再从头与原串比对，如果发现模式串超出原串的右边边界，则查找失败，返回 -1。用一张图来描述就是这样子的：
由于这是一个 DNA 配对的例子，所以模式串的每个碱基（字符）都需要转换为相应的互补碱基后再执行算法。比如说，模式串为“CTTAAG”需要先转换为“GAATTC”
将这个过程写成代码的形式：
def string_matching_bf(text, pattern):
pattern = convert(pattern) # 转换模式串
n = len(text); m = len(pattern) # 原串和模式串的长度
for i in range(n-m+1):
j = 0 # 记录配对成功的字符数
while j < m and pattern[j] == text[i+j]:
j += 1
if j == m: # 配对成功
return i
return -1 # 配对失败
# 转换碱基对
def convert(ori_text):
dic = {'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}
temp = []
for char in ori_text:
conv_char = dic[char]
temp.append(conv_char)
conv_text = ''.join(temp)
return conv_text
其中原串的长度为 n，模式串长度为 m。接下来我们分析一下算法的复杂度。先来看看最好的情况，最好的情况当然就是一次就成功啦，所以只需要比较 m 次，时间复杂度就为 Θ(m)。最坏的的情况就是，模式串每向右移动一个单位，都需要比较 m 次，一共要移动 (n-m+1) 次。所以在最坏的情况下一共需要比较 m(n-m+1) 次，一般来讲，n 要远远大于 m，故时间复杂度就为 Θ(mn)。
在自然语言中，通常原串和模式串的第一次比对失败的概率很大，所以每次模式串向右移动的一个单位时候所需要比较的次数接近于 1，因此在平均情况可以视为一个线性的复杂度：Θ(n)。
→ 本节全部代码 ←
