2 ms·
Unfortunately the real world version of this would have to deal with at least case folding, and most likely the oddities of specific languages and unicode (like
by rwmj 4y ago
Unfortunately the real world version of this would have to deal with at least case folding, and most likely the oddities of specific languages and unicode (like all the ways to represent the "same" letters and numbers, ß in German, narrow and wide katakana etc). I wonder if SIMD can help with this or if it's just too complicated?
- burntsushi 4y agoIt would not. Real world versions of what you speak would use different algorithms. If you're concerned about different normalization forms for example, the typical way to do that is to normalize both your needle and haystack before doing a search. For case folding, you can enumerate at least all the possible prefixes of small length, scan for those using a SIMD algorithm like Teddy (from Hyperscan) and then use a finite state machine to confirm or reject the match. That's how Rust's regex crate (and consequently, ripgrep) works for example. Regardless of those cases, exact string match is still very much desirable to optimize and is extremely useful in the real world.