Java's String.indexOf is quadratic, and a 4096-character adversarial needle costs 1.1 seconds on a 1 MB string

Sources: Daniel Lemire write-up, HN discussion
Summary: Java's String.indexOf runs in O(n times m) rather than linear time. Lemire measures one call with a 4096-character adversarial needle over a 1 MB string at 1.1 seconds, on OpenJDK 25 on an Apple M4 Max. A Two-Way implementation holds about 0.3 ns per character on the same adversarial input but loses to indexOf on random text.
Why it matters: Any service that runs indexOf with an attacker-supplied needle has a cheap denial-of-service path, and the remedy is a length bound on the needle rather than a different algorithm, because the linear alternative is slower in the normal case.