I have a given byte array in C and I need to match it against several byte arrays and return true if there is any match.
I can make various memcmp's but I feel that it is very inefficient.
Do you know a better way?
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.Sign up to join this community
It's a degenerate DFA without cycles. For implementation you have a
int state and a
int nextState for each state.
For Matching states you would make the state number for it negative so you know when it's reached.
In principle a search Trie is what you want, but you'd have to profile your actual data to find out when that actually performs better (it might always be worse unless you can find a cache-friendly layout).
Edit based on comments:
Are you matching a stream or discrete packets?
If the former, and you need to handle matches spanning the boundary between consecutive byte-arrays, you definitely want ratchet freak's DFA.
If the latter, your tradeoff depends on:
The cache effects I originally mentioned are very platform dependent.
If you have a reasonably-sized fast cache (ie your substrings fit in it), then direct
memcmp may be faster. Profile. You can speed this up by sorting your substrings and using the return value of
memcmp to perform binary search on them.
Especially for an embedded system, if the cache is small or the penalty for missing not that large, or your substrings don't fit in cache anyway, then chasing Trie nodes around is fine
tl;dr - Trie is asymptotically optimal but cache effects may dominate. Measure it!