8月22日、コンピュータサイエンス研究者のDaniel Lemire（カナダ・ケベック大学教授、高性能アルゴリズム研究で知られる）が「Java's String.indexOf can be slow (quadratic)」と題した記事を公開した。この記事では、JavaのString.indexOfメソッドが特定の入力パターンにおいてO(n·m)の二乗オーダーに陥る問題を、詳細なベンチマークとともに解説している。
APIやWebフォームで外部から文字列を受け取るシステムを構築しているJava開発者にとって、これは見過ごせない問題だ。悪意あるユーザーが長い検索文字列を送り込むだけで、サーバーの処理を数秒単位で止められる可能性がある。Lemireはこれをセキュリティ上の問題というより「知っておくべきパフォーマンス特性」として扱っているが、外部入力を制御しないシステムではDoS的な状況を招くリスクがある。
String.indexOfのどこが問題なのか
Javaでは文字列内の部分文字列を探すのに indexOf を使う。
String haystack = "The quick brown fox jumps over the lazy dog";
String needle = "fox";
int index = haystack.indexOf(needle);
素朴な実装は二重ループになる。
int naiveIndexOf(String haystack, String needle) {
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
int j = 0;
for (; j < needle.length()
&& haystack.charAt(i + j) == needle.charAt(j); j++) {}
if (j == needle.length()) { return i; }
}
return -1;
}
Javaの実際の indexOf 実装はこれより高度で、大幅に最適化されている。しかし、特定の入力に対しては最悪ケースでO(n·m)の計算量に陥る。n がhaystack（検索対象文字列）の長さ、m がneedle（検索する部分文字列）の長さだ。
実測値で見る二乗の恐怖
問題が顕在化するのは、haystackとneedleの両方が長くなる場合だ。Lemireは以下のような「敵対的入力」を使って計測した。
// n > m
String haystack = "a".repeat(n);
String needle = "a".repeat(m - 1) + "b";
a を大量に並べたhaystack（1メガバイト）に対し、最後の1文字だけ異なるneedleを検索するパターンだ。ミスマッチが最後まで判明しないため、比較回数が爆発する。
計測環境はOpenJDK 25 / Apple M4 Max（Apple Silicon）。なお、現行LTSであるJDK 21でも同様の挙動が確認されており、特定のビルドに限った問題ではない。数値はhaystack 1文字あたりのナノ秒。
| m（needle長） | indexOf（ns/文字） |
|---|---|
| 512 | 140 |
| 1024 | 273 |
| 2048 | 543 |
| 4096 | 1076 |
needle長が2倍になるたびに処理時間がほぼ2倍に増える。m = 4096の時点で、1メガバイトに対する1回の検索に約1.1秒かかる。needleが長くなるほど遅くなるのは直感に反するかもしれないが、これがO(n·m)の実態だ。
Two-Wayアルゴリズムとの比較
この問題の教科書的な解法は、CrochemoreとPerrinが1991年に提案したTwo-Wayアルゴリズムだ（論文：Two-Way String-Matching, JACM 1991）。線形時間O(n+m)での検索を保証する。検索前にneedleを解析して「どこまで読み進めたら安全に読み直せるか」を事前計算することで、最悪ケースでも比較回数を線形に抑える仕組みだ。
同じ敵対的入力での比較がこちら。
| m | indexOf（ns/文字） | Two-Way（ns/文字） |
|---|---|---|
| 8 | 0.44 | 0.29 |
| 32 | 0.48 | 0.29 |
| 128 | 0.45 | 0.30 |
| 256 | 73.9 | 0.32 |
| 1024 | 273 | 0.32 |
| 4096 | 1076 | 0.31 |
Two-Wayはneedle長にかかわらず約0.3 ns/文字で一定を保つ。m = 4096の時点で indexOf の約3500倍速い。
ではTwo-Wayに乗り換えるべきか？
答えはNoだ。ランダムなテキストに対しては indexOf の方がずっと速い。
| m | indexOf（ns/文字） | Two-Way（ns/文字） |
|---|---|---|
| 8 | 0.30 | 0.55 |
| 64 | 0.10 | 0.56 |
| 256 | 0.24 | 0.53 |
| 4096 | 0.22 | 0.55 |
Two-Wayは検索前にneedleの前処理が必要で、固定のオーバーヘッドがある。現実のほとんどのユースケースでは indexOf が上回る。JavaのString.indexOfがTwo-Wayを採用していないのはこのトレードオフの結果だ。
実務でどう対処するか
Lemireの結論はシンプルだ。「通常のユースケースでは indexOf で問題ない」。
ただし、外部からneedle（検索文字列）を受け取るシステムを構築している場合は話が変わる。REST APIの検索エンドポイントやフルテキスト検索フォームがその典型例だ。悪意あるユーザーが長いneedleを送り込めば、意図的に処理を遅延させられる可能性がある。対策は「長いneedleを受け付けない」こと。Lemireが指摘するように、実用的な文字列検索のほとんどは短い文字列が対象であり、入力にバウンダリを設けることで問題は回避できる。
本記事のベンチマークに使ったJavaソースコードはGitHubで公開されている。
詳細はJava's String.indexOf can be slow (quadratic)を参照していただきたい。
