第15章
すべての共通接頭辞
（やさしい版）
Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）
どんな話？
2 つの文字列（またはリスト）が、先頭から何文字まで一致しているかを返す関数を llcp（longest common prefix の略）と呼びます。たとえば：
- llcp
"common" "computing" = 3（先頭 3 文字 "com" が一致）
この章のテーマは、そこから派生した allcp（all the common prefixes）という関数です。allcp xs は、xs と、xs のあらゆる末尾（tails）との間で、一致する接頭辞の長さをまとめて返す関数です。
allcp xs = map (llcp xs) (tails xs)
Dart
// 素直な定義。xs と、xs の各末尾（空でない）との llcp を並べる。
int llcpNaive(List<int> xs, List<int> ys) {
final n = xs.length < ys.length ? xs.length : ys.length;
var i = 0;
while (i < n && xs[i] == ys[i]) i++;
return i;
}
List<int> allcpNaive(List<int> xs) {
final n = xs.length;
return [for (var i = 0; i < n; i++) llcpNaive(xs, xs.sublist(i))];
}
ここで tails xs は「xs の空でない末尾部分列」を全部集めたもの。たとえば xs = abacabacab（長さ 10）に対しては：
読み方
たとえば 5 番目（0 始まり）の 6 は、xs = abacabacab と、5 文字目から始まる末尾 abacab とを比べたとき、先頭 6 文字 abacab が一致していることを表しています。0 番目は xs 自身との比較なので、当然 length xs = 10 になります。
この章のゴール
- 素直に定義どおり計算すると O(n²) かかる。
- これを O(n) の線形時間で計算する方法を導く。
allcp は文字列検索の Boyer–Moore アルゴリズムの重要な部品でもあります（次章のテーマ）。だから、線形時間で解けることには実用的な意味もあります。
速くするためのカギ
llcp の三角不等式のような性質
高速化の土台となるのは、llcp の次の性質です。3 つのリスト us, vs, ws について、llcp us vs = m、llcp vs ws = n だとすると、
llcp us ws = { min m n if m ≠ n
{ m + llcp (drop m us) (drop m ws) if m = n(15.1)
直感的な説明
- 最初の min m n 文字は、us, vs, ws のいずれにも共通です（vs を中継してつながっている）。
- m < n のとき：us の m 文字目は vs と食い違うが、vs と ws の m 文字目は一致。だから us と ws も m 文字目で食い違い、llcp us ws = m。
- m > n のとき：対称の議論で llcp us ws = n。
- m = n のときだけは、そこから先はまだ一致しているかもしれないので、続けて調べる必要がある。
この性質を allcp の計算に使う
n = length xs とし、1 ≤ i, j < n を取って、
p = llcp xs (drop i xs) … allcp xs の i 番目の値
q = llcp xs (drop j xs) … allcp xs の j 番目の値
とおきます。さらに j ≤ p と仮定すると、llcp の定義から
p = j + llcp (drop j xs) (drop (i+j) xs)
が成り立ちます。us = xs、vs = drop j xs、ws = drop k xs（ただし k = i+j）とおいて (15.1) を適用すると、
llcp xs (drop k xs) = { min (p−j) q if q ≠ p−j
{ q + llcp (drop q xs) (drop (q+k) xs) if q = p−j
ここが嬉しい
allcp xs の
k 番目の値を、
すでに計算済みの i 番目と j 番目の値から求められる、ということです。
- 第 1 節（q ≠ p−j）：追加の照合は 0 回で済む（値がすぐ決まる）。
- 第 2 節（q = p−j）：少し追加の照合が必要（それでもゼロから照合するよりずっと少ない）。
ただし、この近道が効くのは
1 < i < k かつ j = k−i < p のときだけ。
k = 0 と
k = 1 の場合は直接計算するしかありません。
i の選び方の戦略
k = 1, 2, …, n の順に計算していきます。各ステップで i を選ぶルールは：
- 1 ≤ i < k の範囲で、i + p ができるだけ大きくなるように選ぶ。
- k < i + p なら、上の近道が j = k − i で使える。
- k ≥ i + p の場合は、素直に llcp xs (drop k xs) を計算する（近道なし）。
初期値は (i, p) = (0, 0) にしておくと、k = 1 は必ず直接計算になります。以降、より大きな i + p が見つかるたびに (i, p) を更新します。
最初のプログラム
上の考えをそのまま書き下すと、図 15.1 のような単純なループになります。
Dart
// 状態は (as, i, p, k) の 4 つ組。as は答えのリスト、(i, p) は
// 「これまでで i + p が最大になる i とそのときの p」、k は今処理する位置。
int llcpList(List<int> xs, List<int> ys) {
final n = xs.length < ys.length ? xs.length : ys.length;
var i = 0;
while (i < n && xs[i] == ys[i]) i++;
return i;
}
List<int> allcpFirst(List<int> xs) {
final n = xs.length;
final as = <int>[n]; // as は snoc（末尾追加）で伸ばす
var i = 0, p = 0, k = 1;
while (k != n) {
if (k >= i + p) {
final a = llcpList(xs, xs.sublist(k));
as.add(a);
i = k; p = a;
} else {
final q = as[k - i]; // as !! (k - i)
final r = p - (k - i);
if (q != r) {
as.add(q < r ? q : r); // 追加照合なし
} else {
final b = q + llcpList(xs.sublist(q), xs.sublist(q + k));
as.add(b);
i = k; p = b;
}
}
k++;
}
return as;
}
正しく更新できているか
- 第 1 節：k ≥ i+p ⇒ k+a ≥ i+p（新しい k+a が現状の i+p 以上になっている）。
- 第 3 節：k+b ≥ k+q = i+p。
なぜ線形時間？
計算量の見積もり
snoc、!!、
drop がすべて
定数時間で行えると仮定します（この仮定を成り立たせるのが後半の仕事）。
そのとき
llcp の中で行われる
等値比較の総数が
n に比例することを言えば十分です。
- 不一致（False）：step の 1 回の呼び出しで最大 1 回。呼び出し回数は n − 1 なので、不一致は最大 n − 1 回。
- 一致（True）：あるステップで m 回の一致が起きたら、i+p の値は少なくとも m だけ増える。i+p は n を超えないので、一致の総数も高々 n 回。
合わせて
O(n) の比較で済みます。
データ精緻化 ― 定数時間の操作にする
ところが、snoc、(!!)、drop は、そのままでは定数時間ではありません。以下は、これらを本当に定数時間で実装するためのデータ精緻化（データ構造の置き換え）です。
drop を配列で置き換える
まず drop。ここでは Haskell の配列ライブラリ Data.Array を使い、xa = listArray (0, n − 1) xs という大域配列を用意します。drop を使う代わりに、配列の添字を直接指定して llcp を書き直します。
llcp′ j k | j == n ∨ k == n = 0
| xa ! j == xa ! k = 1 + llcp′ (j + 1) (k + 1)
| otherwise = 0
Dart
// 添字だけで llcp を測る。xa は入力列を配列化した大域データ。
int llcpArr(List<int> xa, int j, int k) {
final n = xa.length;
var count = 0;
while (j < n && k < n && xa[j] == xa[k]) {
j++; k++; count++;
}
return count;
}
これで、step の a と b はもう drop を使わずに書けます。
a = llcp′ 0 k
b = q + llcp′ q (q + k)
snoc と (!!) をどうする？
残るは snoc（末尾追加）と (!!)（添字参照）。素直には「これも配列で」と思うところですが、うまくいきません。
- 普通の配列：末尾追加を定数時間にするには全体をモナドに包む必要がある（避けたい）。
- Data.Sequence：snoc は定数時間だが、添字参照が対数時間しかかからない（線形時間解を目指すなら惜しい）。
そこでの解決策はキューを使うこと。しかも 2 本使います。
Okasaki のキュー
Chris Okasaki の純関数型キュー（Okasaki, 1995）が備える 4 つの演算：
insert :: Queue a → a → Queue a
remove :: Queue a → (a, Queue a)
empty :: Queue a
elems :: Queue a → [a]
- insert：末尾に要素を追加。
- remove：先頭要素と残りのキューを返す。
- empty：空のキュー。
- elems：キューの要素一覧をリストで返す。
計算量
insert, remove, empty は 定数時間。elems はキュー長に比例した時間がかかります（最後に 1 回だけ呼ばれる想定）。
2 本のキューで置き換える
- 成分 as（これまでの答えを蓄えるリスト）をキューに置き換え、そのまま as と呼ぶ。
- 2 本目のキュー qs を追加。qs は末尾列 drop (k−i) as を表す。すると q = as !! (k − i) は qs の先頭要素として得られる（定数時間）。
- 引数 i は不要になり、代わりに h = i + p を持つ。
最終形
Dart
// Dart では配列 as と「窓の先頭」を示すインデックス i で表現。
// これで snoc / as!!(k-i) / drop 相当がすべて定数時間になる（O(n) 全体）。
// 変数対応：h = i + p、qs は as[k-i..] を表す（実体は持たず添字だけ）。
List<int> allcp(List<int> xa) {
final n = xa.length;
if (n == 0) return <int>[];
int llcpPrime(int j, int k) {
var c = 0;
while (j < n && k < n && xa[j] == xa[k]) { j++; k++; c++; }
return c;
}
final as = <int>[n]; // as = [n]
var i = 0, h = 0, k = 1; // h = i + p
while (k != n) {
if (k >= h) {
final a = llcpPrime(0, k);
as.add(a);
i = k; h = k + a; // (i, p) を更新
} else {
final q = as[k - i]; // qs の先頭 = as!!(k-i)
final r = h - k;
if (q != r) {
as.add(q < r ? q : r); // 追加照合なし、h 据え置き
} else {
final b = q + llcpPrime(q, q + k);
as.add(b);
i = k; h = k + b; // (i, p) = (k, b) に更新
}
}
k++;
}
return as;
}
まとめ
すべての操作（配列参照、キューの insert / remove）が定数時間になり、全体で O(n) 時間で allcp xs を計算できます。最後の elems as だけは n に比例する時間がかかりますが、それも線形時間の範囲内です。
Dart
// 動作確認: xs = "abacabacab" を数値列に変換して allcp を求める
void main() {
final xs = 'abacabacab'.codeUnits;
print(allcpNaive(xs)); // [10, 0, 1, 0, 6, 0, 1, 0, 2, 0]
print(allcpFirst(xs)); // 同上
print(allcp(xs)); // 同上（最終形・O(n)）
}
結びに
allcp を計算する問題は、Gusfield (1997) では文字列照合の基本的な前処理として扱われ、そこでは「Z アルゴリズム」の名で知られています。Crochemore と Rytter も同じ問題を「接頭辞の表（table of prefixes）」として扱っています。
本章の扱いはおおむね Gusfield に沿ったものですが、次の 2 点が独自の工夫です。
- (15.1) を llcp の鍵となる性質として明示的に取り出したこと。
- snoc と !! を効率的にするためにキューを使ったこと。
参考文献
Crochemore, M. and Rytter, W. (2003). Jewels of Stringology. Hong Kong: World Scientific.
Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences. Cambridge, UK: Cambridge University Press.
Okasaki, C. (1995). Simple and efficient purely functional queues and deques. Journal of Functional Programming, 5 (4), 583–92.