Errata では、訂正前と訂正後のテキストの差分を表示するために最長共通部分列(LCS)を抽出しています。LCS を計算するためのアルゴリズムはいくつか知られており、これまでは Gauche の util.lcs モジュールで実装されている O(ND) のものを移植して使っていました。
今回 S. Wu, U. Manber, G. Myers, and W. Miller, "An O(NP) Sequence Comparison Algorithm" (1989) に書かれているアルゴリズムを検討してみました。それによると、O(ND) よりも O(NP) の方が最悪のケースで2倍程度、差分が大きい場合にはさらにより効率がよいということです。再利用出来るように R6RS のライブラリとしてプログラムを作成しました: http://github.com/tabe/lcs
実際どれくらい性能が出ているかを計測するのは今後の課題です。