而要是 old 在匹配途中失败了，会发生什么事呢？举例来说，假设我们要找的模式 (pattern)是 "abac" ，而输入文件包含的是 "ababac" 。输入会一直到第四个字符才发现不匹配，也就是在模式中的 c 以及输入的 b 才发现。在此时我们可以将原本的 a 写至输出文件，因为我们已经知道这里没有匹配。但有些我们从输入读入的字符还是需要留着: 举例来说，第三个 a ，确实是成功匹配的开始。所以在我们要实现这个算法之前，我们需要一个地方来储存，我们已经从输入读入的字符，但之后仍然需要的字符。

一个暂时储存输入的队列 (queue)称作缓冲区 (buffer)。在这个情况里，因为我们知道我们不需要储存超过一个预定的字符量，我们可以使用一个叫做环状缓冲区 ring buffer 的资料结构。一个环状缓冲区实际上是一个向量。是使用的方式使其成为环状: 我们将之后的元素所输入进来的值储存起来，而当我们到达向量结尾时，我们重头开始。如果我们不需要储存超过 n 个值，则我们只需要一个长度为 n 或是大于 n 的向量，这样我们就不需要覆写正在用的值。

在图 7.1 的代码，实现了环状缓冲区的操作。 buf 有五个字段 (field): 一个包含存入缓冲区的向量，四个其它字段用来放指向向量的索引 (indices)。两个索引是 start 与 end ，任何环状缓冲区的使用都会需要这两个索引: start 指向缓冲区的第一个值，当我们取出一个值时， start 会递增 (incremented)； end 指向缓冲区的最后一个值，当我们插入一个新值时， end 会递增。

另外两个索引， used 以及 new ，是我们需要给这个应用的基本环状缓冲区所加入的东西。它们会介于 start 与 之间。实际上，它总是符合

你可以把 used 与 new 想成是当前匹配 (current match) 的 start 与 end 。当我们开始一轮匹配时， used 会等于 start 而 new 会等于 end 。当下一个字符 (successive character)匹配时，我们需要递增 used 。当 used 与 new 相等时，我们将开始匹配时，所有存在缓冲区的字符读入。我们不想要使用超过从匹配时所存在缓冲区的字符，或是重复使用同样的字符。因此这个 new 索引，开始等于 end ，但它不会在一轮匹配我们插入新字符至缓冲区一起递增。

要插入一个新值至缓冲区，我们将使用 buf-insert 。它将 end 递增，并把新的值放在那个位置 (译注: 递增完的位置)。相反的 buf-pop 返回一个缓冲区的第一个数值，接着将 start 递增。任何环状缓冲区都会有这两个函数。

图 7.1 环状缓冲区的操作

接下来我们需要两个特别为这个应用所写的函数: buf-next 从缓冲区读取一个值而不取出，而 buf-reset 重置 used 与 new 到初始值，分别是 与 end 。如果我们已经把至 new 的值全部读取完毕时， buf-next 返回 nil 。区别这个值与实际的值不会产生问题，因为我们只把值存在缓冲区。

最后 buf-flush 透过将所有作用的元素，写至由第二个参数所给入的流，而 buf-clear 通过重置所有的索引至 -1 将缓冲区清空。

在图 7.1 定义的函数被图 7.2 所使用，包含了字符串替换的代码。函数 file-subst 接受四个参数；一个查询字符串，一个替换字符串，一个输入文件以及一个输出文件。它创建了代表每个文件的流，然后调用 stream-subst 来完成实际的工作。

变数 pos 指向我们想要匹配的字符在寻找字符串的所在位置。如果 pos 等于这个字符串的长度，我们有一个完整的匹配，则我们将替换字符串写至输出流，并清空缓冲区 (3)。如果在这之前匹配失败，我们可以将缓冲区的第一个元素取出，并写至输出流，之后我们重置缓冲区，并从 pos 等于 0 重新开始 (4)。

图 7.2 字符串替换

下列表格展示了当我们将文件中的 "baro" 替换成 "baric" 所发生的事，其中文件只有一个单字 "barbarous" :

第一栏是当前字符 ── c 的值；第二栏显示是从缓冲区或是直接从输入流读取；第三栏显示需要匹配的字符 ── old 的第 posth 字符；第四栏显示那一个条件式 (case)被求值作为结果；第五栏显示被写至输出流的字符；而最后一栏显示缓冲区之后的内容。在最后一栏里， used 与 new 的位置一样，由一个冒号 ( : colon)表示。

在文件 "test1" 里有如下文字：

为了使这个例子尽可能的简单，图 7.2 的代码只将一个字符串换成另一个字符串。很容易扩展为搜索一个模式而不是一个字面字符串。你只需要做的是，将 char= 调用换成一个你想要的更通用的匹配函数调用。