第17章
Knuth–Morris–Pratt アルゴリズム
（やさしい版）
Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）
どんな話？
この章は、有名な文字列検索アルゴリズム KMP（Knuth–Morris–Pratt）を、関数型プログラミングの流儀で導き出す、という話です。
KMP とは？
「長いテキストの中から、あるパターン（部分文字列）が出てくる位置を全部見つけたい」という定番の問題を、テキストの長さに比例した時間（線形時間）で解くアルゴリズムです。素朴に「1 文字ずつずらして毎回比較」すると遅くなりますが、KMP は失敗したときに賢く戻ることでムダを省きます。
ゴール
やりたいのはこれだけです。関数 matches ws xs を作って、パターン ws がテキスト xs のどこ（何文字目の位置）で終わっているかを、そのすべてリストで返す。
この章の目標
matches を Θ(m + n) 時間（m = パターン長、n = テキスト長）で計算できる形に持っていくこと。設計方針は「foldl の形にできれば、テキストを 1 回なぞるだけで済む」というものです。
はじめに ― 出発点
「末尾に来ているか」を判定する関数
まず endswith ws xs（ws が xs の末尾に一致しているか？）を、xs のすべての接尾辞（tails）に ws が含まれているかどうか、と書くところから始めます。
endswith ws xs = ws ∈ tails xs
Dart
// tails: 各接尾辞を長い順に返す（[xs, tail xs, ..., []]）
Iterable<List<T>> tails<T>(List<T> xs) sync* {
for (var i = 0; i <= xs.length; i++) {
yield xs.sublist(i);
}
}
bool listEq<T>(List<T> a, List<T> b) {
if (a.length != b.length) return false;
for (var i = 0; i < a.length; i++) if (a[i] != b[i]) return false;
return true;
}
bool endswith<T>(List<T> ws, List<T> xs) =>
tails(xs).any((s) => listEq(s, ws));
この道が、実は KMP アルゴリズムにつながっています。目標は、ある関数 p、op と初期値 e を見つけて、endswith ws = p · foldl op e の形にすること。これができれば matches を次のように書けます。
matches :: Eq a ⇒ [a] → [a] → [Int]
matches ws = map fst · filter (p · snd) · scanl step (0, e)
step (n, x) y = (n + 1, op x y)
Dart
// scanl: 初期値 e と二項演算 op を用い、途中結果を全部返す
Iterable<S> scanl<S, T>(S e, S Function(S, T) op, List<T> xs) sync* {
var acc = e;
yield acc;
for (final x in xs) {
acc = op(acc, x);
yield acc;
}
}
// 骨格: p, op, e が定まれば matches はこの形で書ける
List<int> matchesGeneric<S, T>(
S e,
S Function(S, T) op,
bool Function(S) p,
List<T> xs,
) {
(int, S) step((int, S) ns, T y) => (ns.$1 + 1, op(ns.$2, y));
return scanl((0, e), step, xs)
.where((ns) => p(ns.$2))
.map((ns) => ns.$1)
.toList();
}
matches ws xs の値は、パターン ws がテキスト xs の中で「位置 n で終わる」ように出てくるような整数 n のリストです。p と op が定数時間（あるいはならして定数時間）で動けば、全体は Θ(m + n) ステップで済みます。
最初の一歩
素朴な合成から出発
まずは endswith ws を関数合成の形で書いてみます。
endswith ws = not · null · filter (= ws) · tails
Dart
bool endswithV1<T>(List<T> ws, List<T> xs) =>
tails(xs).where((s) => listEq(s, ws)).isNotEmpty;
でも filter (= ws) · tails は foldl の形にできません。理由は、この関数の結果は「空リスト」か「[ws] だけ」の二択しかなく、次の状態を作るための情報が足りないからです。
「接頭辞かどうか」で候補を残す
そこで、より情報量の多い filter (⊑ ws) · tails（⊑ は「接頭辞である」の意）に置き換えます。これを xs に適用すると、ws の接頭辞になっている xs の接尾辞たちを、長い順に全部返します。この列の先頭が ws そのものになるのは、ちょうど endswith ws xs が成り立つときです。
endswith ws = (= ws) · head · filter (⊑ ws) · tails
Dart
// 接頭辞判定 us ⊑ ws
bool isPrefix<T>(List<T> us, List<T> ws) {
if (us.length > ws.length) return false;
for (var i = 0; i < us.length; i++) if (us[i] != ws[i]) return false;
return true;
}
bool endswithV2<T>(List<T> ws, List<T> xs) {
final head = tails(xs).firstWhere((s) => isPrefix(s, ws));
return listEq(head, ws);
}
もう少し情報を持たせる：split
先頭の (= ws) 比較は定数時間ではないので、代わりに split という関数を用意します。
split ws xs = head [(us, ws ↓ us) | us ← tails xs, us ⊑ ws]
Dart
// ws の先頭 us.length 個を落とした残り (ws ↓ us)
List<T> drop<T>(List<T> ws, List<T> us) => ws.sublist(us.length);
(List<T>, List<T>) splitNaive<T>(List<T> ws, List<T> xs) {
final us = tails(xs).firstWhere((s) => isPrefix(s, ws));
return (us, drop(ws, us));
}
ここで演算子 ↓ は (us ++ vs) ↓ us = vs（前半を取り除いて後半を返す）と決めておきます。よって split ws xs は ws を二つに切り分けて (us, vs) を返し、us ++ vs = ws となります。us は「ws の接頭辞になっている xs の最長接尾辞」です。
例
split "endnote" "append" = ("end", "note")。"append" の末尾 "end" はパターン "endnote" の先頭に一致しています。残りの "note" がまだマッチしていない部分です。
これで endswith ws = null · snd · split ws（後半が空なら完全一致）と書けます。あとは split ws = foldl op e となる e と op を見つけるだけです。
split ws [ ] = e
split ws (xs ++ [x]) = op (split ws xs) x
split ws [ ] = ([ ], ws) なので、e = ([ ], ws) と決まります。あとは op を見つけるだけです。
op を見つけるカギとなる観察
重要な観察
もし
split ws xs = (
us,
vs) なら、次を読んで得た結果は元のテキストを直接使う必要がなく、
us ++ [
x] だけから決まります。
split ws xs = (us, vs) ⇒ split ws (xs ++ [x]) = split ws (us ++ [x])
つまり「
ws の接頭辞になっている
xs ++ [
x] の最長接尾辞」は、
us ++ [
x] の接尾辞になっている、ということです。もっと長い接尾辞があったら、
us が最長だという定義に反してしまいます。
この観察を使うために、まず split を再帰的に書き直します。
split ws xs = if xs ⊑ ws then (xs, ws ↓ xs) else split ws (tail xs)
Dart
// 再帰版 split: xs が ws の接頭辞になるまで先頭を落とす
(List<T>, List<T>) splitRec<T>(List<T> ws, List<T> xs) {
if (isPrefix(xs, ws)) return (xs, drop(ws, xs));
return splitRec(ws, xs.sublist(1));
}
そして split ws xs = (us, vs)、ws = us ++ vs のもとで、次のように計算していきます。
split ws (xs ++ [x])
= {上の観察}
split ws (us ++ [x])
= {split の再帰的定義}
if us ++ [x] ⊑ ws then (us ++ [x], ws ↓ (us ++ [x]))
else split ws (tail (us ++ [x]))
= {ws = us ++ vs と ⊑, ↓ の定義から}
if [x] ⊑ vs then (us ++ [x], tail vs)
else split ws (tail (us ++ [x]))
= {us で場合分け}
if [x] ⊑ vs then (us ++ [x], tail vs)
else if null us then ([ ], ws)
else split ws (tail us ++ [x])
これで op の定義が得られました。
op (us, vs) x | [x] ⊑ vs = (us ++ [x], tail vs)
| null us = ([ ], ws)
| otherwise = op (split ws (tail us)) x
Dart
// 状態 (us, vs) と次の 1 文字 x から、新しい分割を作る
(List<T>, List<T>) op<T>(List<T> ws, (List<T>, List<T>) uv, T x) {
final (us, vs) = uv;
if (vs.isNotEmpty && vs.first == x) {
return ([...us, x], vs.sublist(1));
}
if (us.isEmpty) return (<T>[], ws);
return op(ws, splitRec(ws, us.sublist(1)), x); // ムダな再計算あり
}
ここまでのまとめ
matches ws = map fst · filter (null · snd · snd) ·
scanl step (0, ([ ], ws))
step (n, (us, vs)) x = (n + 1, op (us, vs) x)
Dart
// 骨格版 matches (分割 (us, vs) を状態として持ち回す)
List<int> matchesSkel<T>(List<T> ws, List<T> xs) {
final e = (<T>[], ws);
(int, (List<T>, List<T>)) step(
(int, (List<T>, List<T>)) ns,
T y,
) =>
(ns.$1 + 1, op(ws, ns.$2, y));
return scanl((0, e), step, xs)
.where((ns) => ns.$2.$2.isEmpty)
.map((ns) => ns.$1)
.toList();
}
これが KMP アルゴリズムの骨格です。各ステップで「パターン ws の現在の分割 (us, vs)」を持ち回し、us は「これまでのテキストの末尾と一致している ws の最長接頭辞」。vs が空になった位置が「パターンが完全に一致した位置」なので、それを記録します。
問題点
op の 3 番目の枝で split ws (tail us) を計算していますが、これはムダな再計算を引き起こします。パターンの部分列 zs に対する split ws zs を何度も計算してしまうのです。もっと賢い方法が欲しいところです。
データ精緻化（表現の取り替え）
アイデア
効率化のカギは、op に渡す第一引数の表現を取り替えることです。データ精緻化と呼ばれる標準テクニックで、次の 2 つの関数を用意します。
abs :: Rep ([a], [a]) → ([a], [a])
rep :: ([a], [a]) → Rep ([a], [a])
- rep：抽象値（分割 (us, vs)）から、内部表現 Rep を作る「表現関数」。
- abs：内部表現から抽象値に戻す「抽象化関数」。abs · rep = id（つまり abs は rep の左逆）が必要。
次の関係を成り立たせ、しかも abs と op′ が定数時間で動くようにできれば大成功です。
foldl op ([ ], ws) = abs · foldl op′ (rep ([ ], ws))(17.1)
そのとき matches は次のように書き直せます。
matches ws = map fst · filter (null · snd · abs · snd) ·
scanl step (0, rep ([ ], ws))
step (n, r) x = (n + 1, op′ r x)
Dart
// 精緻化版 matches: 状態を Rep 型 R で持つ
List<int> matchesRefined<T, R>(
List<T> ws,
R Function((List<T>, List<T>)) rep,
(List<T>, List<T>) Function(R) abs,
R Function(R, T) opPrime,
List<T> xs,
) {
final e0 = rep((<T>[], ws));
(int, R) step((int, R) ns, T y) => (ns.$1 + 1, opPrime(ns.$2, y));
return scanl((0, e0), step, xs)
.where((ns) => abs(ns.$2).$2.isEmpty)
.map((ns) => ns.$1)
.toList();
}
foldl の融合則を「逆向き」に使う
(17.1) を満たすものを見つけるために foldl の融合則を使います。この法則は普通「合成をひとつの畳み込みにまとめる」向きで使いますが、ここでは逆向き（分裂 / fission）に使い、ひとつの畳み込みを 2 段階に分けます。
2 つ目の融合条件は自明：abs (rep ([ ], ws)) = ([ ], ws)。op′ の自然な選び方は次です。
op′ r = rep · op (abs r)(17.2)
すると次が成り立ちます。
abs (op′ r x) = abs (rep (op (abs r) x)) = op (abs r) x
(17.2) に op の定義を代入すると次を得ます。
op′ r x | [x] ⊑ vs = rep (us ++ [x], tail vs)
| null us = rep ([ ], ws)
| otherwise = op′ (rep (split ws (tail us))) x
where (us, vs) = abs r
Dart
// 一般化された op' (Rep 型 R は後で二分木で具体化する)
R opPrimeGeneric<T, R>(
List<T> ws,
R Function((List<T>, List<T>)) rep,
(List<T>, List<T>) Function(R) abs,
R r,
T x,
) {
final (us, vs) = abs(r);
if (vs.isNotEmpty && vs.first == x) {
return rep(([...us, x], vs.sublist(1)));
}
if (us.isEmpty) return rep((<T>[], ws));
return opPrimeGeneric(
ws, rep, abs, rep(splitRec(ws, us.sublist(1))), x,
);
}
あとは Rep と、abs・rep の中身を決めるだけです。
木で表現する
データ型
関数プログラミングでは効率化にはたいてい何らかの木を使います。ここでも二分木を使います。
data Rep a = Null | Node a (Rep a) (Rep a)
Dart
// Rep 型 (二分木)。Node は遅延生成で循環を許すため late final に。
sealed class Rep<T> {}
class RNull<T> extends Rep<T> {}
class RNode<T> extends Rep<T> {
final (List<T>, List<T>) label;
late final Rep<T> left;
late final Rep<T> right;
RNode(this.label);
}
abs はノードのラベルを返すだけ。定数時間です。
abs (Node (us, vs) ℓ r) = (us, vs)(17.3)
Dart
// abs: ノードのラベルを返すだけ (定数時間)
(List<T>, List<T>) absTree<T>(Rep<T> t) => switch (t) {
RNode<T>(:final label) => label,
_ => throw StateError('abs on Null'),
};
rep は次のようにラベル・左部分木・右部分木を作ります。
rep (us, vs) = Node (us, vs) (left us vs) (right us vs)(17.4)
left [ ] vs = Null
left (u : us) vs = rep (split ws us)
right us [ ] = Null
right us (v : vs) = rep (us ++ [v], vs)
Dart
// rep の素朴版: 左右の部分木を left/right で計算する
Rep<T> repNaive<T>(List<T> ws, (List<T>, List<T>) uv) {
final (us, vs) = uv;
final node = RNode<T>(uv);
node.left = us.isEmpty ? RNull<T>() : repNaive(ws, splitRec(ws, us.sublist(1)));
node.right = vs.isEmpty ? RNull<T>() : repNaive(ws, ([...us, vs.first], vs.sublist(1)));
return node;
}
op′ がぐっとシンプルになる
この rep の選び方の狙いは、op′ が木のリンクをたどるだけで書けるようになる点です。
op′ (Node (us, vs) ℓ r) x | [x] ⊑ vs = r
| null us = root
| otherwise = op′ ℓ x
Dart
// op' が木のリンクをたどるだけになる (root は事前に作る)
Rep<T> opPrimeTree<T>(Rep<T> root, Rep<T> t, T x) {
if (t is RNode<T>) {
final (us, vs) = t.label;
if (vs.isNotEmpty && vs.first == x) return t.right;
if (us.isEmpty) return root;
return opPrimeTree(root, t.left, x);
}
throw StateError('opPrimeTree on Null');
}
ここで root = rep ([ ], ws)。たとえば 1 番目の枝は次のように正当化されます。
op′ (Node (us, vs) ℓ r) x
= {[x] ⊑ vs の場合の op′ の定義}
rep (us ++ [x], tail vs)
= {right の定義と x = head vs}
right us vs
= {rep の定義}
r
他の枝も同様です。さらに op′ Null x = root と決めれば、op′ はもっとすっきりします。
op′ Null x = root
op′ (Node (us, vs) ℓ r) x | [x] ⊑ vs = r
| otherwise = op′ ℓ x
Dart
// op' Null x = root と決めれば場合分けがひとつ減る
Rep<T> opPrimeClean<T>(Rep<T> root, Rep<T> t, T x) {
if (t is RNull<T>) return root;
final node = t as RNode<T>;
final (_, vs) = node.label;
if (vs.isNotEmpty && vs.first == x) return node.right;
return opPrimeClean(root, node.left, x);
}
実行時間について
op′ 単発は定数時間ではありませんが、ならして定数時間です。木 root の高さはパターン長 m。右に降りると高さがちょうど 1 減り、左に飛ぶと高さが増える可能性があります。標準的な償却の議論により、長さ n のテキストに対する foldl op′ root の呼び出し回数は高々 2m + n になります。
rep を効率よく作る
累積引数のテクニック
残る問題は rep をどう作るか。ここで最後の標準技法、累積引数が登場します。grep という一般化版を次のように定めます。
rep (us, vs) = grep (left us vs) (us, vs)
Dart
// 累積引数版: 左部分木 l を外から渡す
Rep<T> repFromGrep<T>(List<T> ws, (List<T>, List<T>) uv) {
final (us, vs) = uv;
final l = us.isEmpty ? RNull<T>() : repFromGrep(ws, splitRec(ws, us.sublist(1)));
return grepNaive(ws, l, uv);
}
// 後方参照 (次のブロックで定義される grep の呼び出し)
Rep<T> grepNaive<T>(List<T> ws, Rep<T> l, (List<T>, List<T>) uv) {
final (us, vs) = uv;
final node = RNode<T>(uv)..left = l;
node.right = vs.isEmpty ? RNull<T>() : repFromGrep(ws, ([...us, vs.first], vs.sublist(1)));
return node;
}
(17.4) より次が成り立ちます。
grep ℓ (us, vs) = Node (us, vs) ℓ (right us vs)
Dart
// grep はラベルと左部分木 l を受け取り、右部分木を right で構成する
// (実装は上の grepNaive と同じ)
right の定義から right us [ ] = Null、そして次の展開ができます。
right us (v : vs) = rep (us ++ [v], vs)
= grep (left (us ++ [v]) vs) (us ++ [v], vs)
left (us ++ [v]) vs を簡単にする
us で場合分けします。まず us = [ ] の場合：
left ([ ] ++ [v]) vs
= {left の定義}
rep (split ws [ ])
= {split の定義}
rep ([ ], ws)
= {root の定義}
root
次に帰納段階（u : us）：
left (u : us ++ [v]) vs
= {left の定義}
rep (split ws (us ++ [v]))
= {split の定義}
rep (op (split ws us) v)
= {op′ の定義 (17.2)}
op′ (rep (split ws us)) v
= {left の定義}
op′ (left (u : us) vs) v
まとめると次のように書けます。
left (us ++ [v]) vs = if null us then root else op′ (left us vs) v
Dart
// 左部分木は「1 手前の左部分木」から op' で得られる
// left (us ++ [v]) vs =
// us が空なら root、そうでなければ op'(left us vs, v)
// この漸化式が grep を線形時間にするカギ。
したがって grep は次のように定義できます。
grep ℓ (us, [ ]) = Node (us, [ ]) ℓ Null
grep ℓ (us, v : vs) = Node (us, v : vs) ℓ
(grep (op′ ℓ v) (us ++ [v], vs))
Dart
// grep の効率版: 左部分木を持ち回しつつ、右へ進むたびに op' で更新する
Rep<T> grepEfficient<T>(
Rep<T> root,
Rep<T> l,
(List<T>, List<T>) uv,
) {
final (us, vs) = uv;
final node = RNode<T>(uv)..left = l;
if (vs.isEmpty) {
node.right = RNull<T>();
} else {
final v = vs.first;
node.right = grepEfficient(
root, opPrimeClean(root, l, v), ([...us, v], vs.sublist(1)),
);
}
return node;
}
最終プログラム
us は要らない！
ここまでの定義の右辺をよく見ると、対 (us, vs) の第一成分 us は一度も使われていないことが分かります。値が読まれる場面がないのです。というわけで us をきれいに落として、最終プログラムを得ます。
Dart
// KMP 最終版: 木のノードは「残りパターン vs」だけを持てば良い (us は不要)
sealed class KmpTree<T> {}
class KNull<T> extends KmpTree<T> {}
class KNode<T> extends KmpTree<T> {
final List<T> vs; // 残りパターン
late final KmpTree<T> l; // 失敗時に飛ぶ先 (循環リンク)
late final KmpTree<T> r; // 1 文字マッチしたときの遷移先
KNode(this.vs);
}
bool ok<T>(KmpTree<T> t) => t is KNode<T> && t.vs.isEmpty;
// op: 現在の木 t と入力 x から次の木を返す (ならして定数時間)
KmpTree<T> kmpOp<T>(KmpTree<T> root, KmpTree<T> t, T x) {
if (t is KNull<T>) return root;
final node = t as KNode<T>;
if (node.vs.isEmpty) return kmpOp(root, node.l, x);
return node.vs.first == x ? node.r : kmpOp(root, node.l, x);
}
// root と grep を作る (循環参照のため late final を使う)
KmpTree<T> buildRoot<T>(List<T> ws) {
late KmpTree<T> root;
KmpTree<T> grep(KmpTree<T> l, List<T> vs) {
final node = KNode<T>(vs)..l = l;
node.r = vs.isEmpty ? KNull<T>() : grep(kmpOp(root, l, vs.first), vs.sublist(1));
return node;
}
root = grep(KNull<T>(), ws);
return root;
}
List<int> matches<T>(List<T> ws, List<T> xs) {
final root = buildRoot(ws);
(int, KmpTree<T>) step((int, KmpTree<T>) ns, T y) =>
(ns.$1 + 1, kmpOp(root, ns.$2, y));
return scanl((0, root), step, xs)
.where((ns) => ok(ns.$2))
.map((ns) => ns.$1)
.toList();
}
この木の正体
root は循環的な木（グラフ）です。左部分木は木の中の「もっと早い位置のノード」を指すか、Null を指しています。この構造こそが、KMP アルゴリズムの失敗関数を循環グラフの形でカプセル化したものにほかなりません。
実行時間まとめ
- 等価性比較を定数時間と仮定すると、op はならして定数時間。
- root を作るのに Θ(m) ステップ（m = パターン長）。
- その後、長さ n のテキストを走査するのに Θ(n) ステップ。
- 合計 Θ(m + n)。まさに KMP！
Morris–Pratt から本物の KMP へ
もうひと工夫：next 関数
実はここまでのプログラムは、厳密には完全な KMPではなく、Morris–Pratt アルゴリズムに相当するものです。本物の KMP にはもう一段の工夫があります。next という関数を導入します。
next Null x = Null
next (Node [ ] ℓ r) x = Node [ ] ℓ r
next (Node (v : vs) ℓ r) x = if v == x then next ℓ x
else Node (v : vs) ℓ r
Dart
// next: 左リンクをたどり、ラベルが x で始まらない最初の木を返す
KmpTree<T> kmpNext<T>(KmpTree<T> t, T x) {
if (t is KNull<T>) return t;
final node = t as KNode<T>;
if (node.vs.isEmpty) return node;
if (node.vs.first == x) return kmpNext(node.l, x);
return node;
}
要するに next t x は、木 t の左部分木を順にたどっていき、ラベルが x で始まらない最初の木に置き換える働きをします。op の定義から次が成り立つのがポイントです。
op (Node (v : vs) ℓ r) x = op (Node (v : vs) (next ℓ v) r) x
つまり、木の各ノード Node (v : vs) ℓ r をあらかじめ Node (v : vs) (next ℓ v) r に置き換えておけば、失敗時のジャンプを 1 段ずつ試すのを省けて、op をさらに速くできます。詳しくは踏み込みませんが、これが KMP と MP の違いです。
Dart
// 動作確認: パターン "abab" をテキスト "ababcabababab" から検索
void main() {
final ws = 'abab'.split('');
final xs = 'ababcabababab'.split('');
// 最終版 KMP: パターン一致が終わった位置 (1 始まり) のリスト
print(matches(ws, xs));
// [4, 8, 10, 12]
// 骨格版と結果が一致することの簡易チェック
print(matchesSkel(ws, xs));
// [4, 8, 10, 12]
}
参考ノート
KMP アルゴリズムは Knuth ら (1977) が最初に記述したものですが、他にも多数の解説があります（Gusfield 1997、Cormen ら 2001、Crochemore–Rytter 2002 など）。文字列照合、特に KMP と BM に関する論文は 100 を超えます。著者ら自身も KMP について過去に 2 本の論文を書いており（Bird 1977、Bird ら 1989）、1 本は 30 年以上前、関数プログラミングの法則がまだ整理される前のものです。本章の提示は Bird ら (1989) を洗練・改訂した版です。
近年は Olivier Danvy と BRICS の同僚が、部分評価によって KMP や BM を導く一連の研究を進めています。Ager ら (2003) は Bird (1977) と同じ発想で、素朴なアルゴリズムから線形時間の部分評価で KMP を得るという長年の未解決問題を解きました。Danvy–Rohde (2005) は「悪い文字規則」を束縛時間の改善として捉え直し、部分評価で BM の探索段階を導いています。
参考文献
Ager, M. S., Danvy, O. and Rohde, H. K. (2003). Fast partial evaluation of pattern matching in strings. BRICS Report Series, RS-03-11, University of Aarhus, Denmark.
Bird, R. S. (1977). Improving programs by the introduction of recursion. Communications of the ACM 20 (11), 856–63.
Bird, R. S., Gibbons, J. and Jones, G. (1989). Formal derivation of a pattern matching algorithm. Science of Computer Programming 12, 93–104.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001). Introduction to Algorithms, second edition. Cambridge, MA: MIT Press.
Crochemore, M. and Rytter, W. (2002). Jewels of Stringology. Hong Kong: World Scientific.
Danvy, O. and Rohde, H. K. (2005). On obtaining the Boyer–Moore string-matching algorithm by partial evaluation. BRICS Research Report RS-05-14, University of Aarhus, Denmark.
Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences. Cambridge, UK: Cambridge University Press.
Knuth, D. E., Morris, J. H. and Pratt, V. B. (1977). Fast pattern matching in strings. SIAM Journal on Computing 6, 323–50.