3 ms·
Assuming your pattern is static, it shouldn't be much slower. String matching can be done in linear time with some preprocessing: check out Knuth-Morris-Pratt a
by mehrdada 11y ago
Assuming your pattern is static, it shouldn't be much slower. String matching can be done in linear time with some preprocessing: check out Knuth-Morris-Pratt and Boyer-Moore algorithms.
Basically, the idea is that you build a deterministic finite state automaton and try feeding the string through it. Each character would cause exactly one automaton transition. Therefore, you can do the whole thing in O(n) after you pay the cost of preprocessing to build the automaton, with a quite tiny constant for small patterns.
- weinzierl 11y agoActually Boyer-Moore (somewhat counter intuitively) is faster for longer search strings than for short ones. It makes sense if you think about a search string that has the same length as the searched string. If they don't match you can find that out with a single character comparison.
- lqdc13 11y agoIt's much slower because you are checking the first character in all zeros string, but checking multiple characters in the case that the first ones match using Boyer-Moore.