4 ms·
If removing it would complicate the code, then it is part of the algorithm. String APIs are critical to the discussion of algorithm costs, e.g. removing the fi
by joosters 5y ago
If removing it would complicate the code, then it is part of the algorithm.
String APIs are critical to the discussion of algorithm costs, e.g. removing the final character from a string is O(n) if they are null terminated, or O(1) if the string stores its size. Assuming the best of both worlds by ignoring strlen costs is hand-waving away a lot of the real world performance.
- OskarS 5y agoThe fact that C strings are presented in this format is totally irrelevant for the discussion of string search algorithms. They all have to know the length. Strings in most languages are not in that format, and it is an entirely reasonable assumption that the length is a known quantity. If you wanna be annoying about this, just imagine he's implementing `strnstr` instead of `strstr`.
- delusional 5y agoTo me it looks like you could quite easily convert this strstr function to look for 0 bytes. You don't even need to know the length up front. It's just used to make some of the loop bounds more clear.
- deleted 5y ago[deleted]