虽然使用后缀树进行精确模式匹配速度很快，但如何使用后缀树进行近似模式匹配还不清楚。 1994 年，Michael Burrows 和 David Wheeler 发明了一种巧妙的文本压缩算法，即现在的 Burrows-Wheeler Transform。他们对基因组学一无所知，也无法想象 15 年后他们的算法会成为生物学家搜索基因组突变的主力。但是，文本压缩与模式匹配有什么关系呢？在这一课中，你将了解到算法的命运往往难以预测--它的应用可能出现在与发明者最初计划毫不相干的领域。

恭喜你，现在你已经学会了关键的模式匹配概念：尝试、后缀树、后缀数组，甚至 Burrows-Wheeler 变换！然而，帕维尔提到的一些结果仍然令人费解：例如，我们如何能在 O(|Text|) 时间内完成精确模式匹配，而不是像天真的蛮力算法那样在 O(|Text|*|Pattern|) 时间内完成精确模式匹配？根据人类基因组匹配 1000 个核苷酸的模式怎么可能和匹配 3 个核苷酸的模式一样快？此外，尽管 Pavel 展示了如何在给定后缀树的情况下快速构建后缀数组，但他并没有揭示构建后缀树的快速算法背后的奥妙！在本模块中，Miсhael 将解决 Pavel 试图向你隐瞒的一些算法难题：）例如精确模式匹配的 Knuth-Morris-Pratt 算法，以及后缀树和后缀数组构建的更高效算法。

在本模块中，我们将继续研究字符串算法的算法挑战。您将学习后缀数组构造的 O(n log n) 算法，以及从后缀数组构造后缀树的线性时间算法。您还将在本课程的最后一个编程作业中实现这些算法和 Knuth-Morris-Pratt 算法。