I wonder if it's possible to construct an edge-case so that nearly every dictionary lookup results in a match, requiring you to do the string comparison on each

I wonder if it's possible to construct an edge-case so that nearly every dictionary lookup results in a match, requiring you to do the string comparison on each lookup if you want a guaranteed zero false-positive rate? My initial hunch was an example where every prefix of the word is part of the dictionary, then on an example like `abcdefgh` you'd test `a`, `ab,` `abc,`... But on such a case you can be clever and defer the string match until you verify that the hash of the suffix also exists in the dictionary, which it won't. So it would seem a pathological example needs both prefix and suffix matches, but this just means that it's very easy for us to find a valid segmentation, so we will find one very early on. I guess this is probably what you meant by "split would correspond to a good partial match" though.