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).

  • ssh-{rsa|dsa|ed25519}
  • ecdsa-sha2-{nistp256|nistp521}
  • ---- BEGIN SSH2 PUBLIC 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 s, e, or -, 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)?

  • $\begingroup$ If your question is about C++, it is off-topic on this site (but could be asked on e.g., Stack Overflow). If you have an algorithmic question, please remove references to C++ from your question and make it even more focused. $\endgroup$ – Juho Sep 3 '19 at 16:38
  • $\begingroup$ "My question is, is there an algorithm that runs in better time than O(n+sm)" $\endgroup$ – user109143 Sep 3 '19 at 16:41
  • $\begingroup$ You can use regular expressions. All modern programming languages have library support for matching regular expressions. $\endgroup$ – Yuval Filmus Sep 3 '19 at 17:47
  • $\begingroup$ Thanks @Yuval. I don't belive C++03 has regular expressions. They did not debut until C++11. $\endgroup$ – user109143 Sep 3 '19 at 18:45
  • $\begingroup$ gnu.org/software/libc/manual/html_node/Regular-Expressions.html $\endgroup$ – Yuval Filmus Sep 3 '19 at 18:47

You can turn that search into a DFA,and you can then pass the input through the DFA until an accepting state is reached (or the end of the string is encountered).

Each pattern is turned into an NFA by adding a start state which self-loops on any input and transitions to the next state on a match of the first character. Each subsequent state transitions only on the corresponding match. The last state is accepting.

These NFAs are then combined into a single NFA by merging the start states, after which the consolidated NFA is turned into a DFA using subset construction.

Assuming the DFA is stored in a datastructure which allows O(1) transitions, the scan can be performed in $O(k)$ where $k$ is the index of the last character in the earliest match.

Note that this is not a general algorithm. It actually produces the index of the match which ends first, not the one which starts first. In the case where no pattern matches a substring of any other pattern, however, these are the same match so there is no problem.

Also, in the worst case the subset construction takes exponential time, although this is ameliorated by the fact that no pattern use repetition operators. In your particular problem, though, the DFA only needs to be constructed once when the program is compiled and the runtime is going to be $O(n)$.

  • $\begingroup$ Thanks @gnasher. Sorry, I am not allowed to upvote the answer. $\endgroup$ – user109143 Sep 4 '19 at 12:10

The shortest string you accept is seven letters, so you must examine at least one out of every 7 letters. That’s the minimum. So you need to examine at least n/7 letters in the worst case. Which is O(n).

And if the length of the longest string S is k, we can show that in the worst case you need to examine all letters when n is a multiple of k: Create a string consisting of copies of S, except when you have examined k-1 of the letters of one copy, and examine the last remaining letter, that letter is modified. So it takes n steps in the worst case.

  • $\begingroup$ Thanks @gnasher. Sorry, I am not allowed to upvote the answer. $\endgroup$ – user109143 Sep 4 '19 at 12:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.