I am using C++03. I have a stream of chars and I need to find the first token from a group of tokens. That is, I need to find the lowest indexed match. Specifically, the stream is just an char array, and the tokens of interest are listed below. The start of a token can occur anywhere in the stream (and not necessarily at position 0).
- ---- BEGIN SSH2 PUBLIC KEY ----
- -----BEGIN RSA PRIVATE KEY-----
- -----BEGIN DSA PRIVATE KEY-----
- -----BEGIN EC PRIVATE KEY----- (ecdsa)
- -----BEGIN OPENSSH PRIVATE KEY----- (ed25519)
The OpenSSH folks were not very forward thinking, and it is making the lexer/parser more complicated than it should be.
There are some suggestions for the problem like at Pass multiple strings to the string::find function on Stack Overflow. It provides a match for a string, but it may not be the lowest index for a match.
I think my non-STL alternative is to examine each char byte-by-byte. That takes O(n). If the char is one of
-, then look for the longer token, like
ssh-rsa. The full token compare takes O(m) and it may happen s times, so the operation is O(s*m).
I kind of feel like O(n+sm) can be improved upon similar to the way Boyer-Moore improves a single string search. My question is, is there an algorithm that runs in better time than O(n+sm)?