I cannot access the setter's and tester's solutions at the moment, so I am not entirely sure, but, from reading the editorial, it seems that the algorithmically interesting part (deciding if a string matches a regular expression) was "delegated" to the regex.h ~~library. ~~header/library. What is the time complexity of:
1) "compiling" a regular expression ? (I am using the term from the editorial)
2) deciding if a given string matches the regular expression ?
For me, efficiently deciding if a given string matches the regular expression was the most interesting part of the problem. I first built an evaluation tree for the expression (although not in linear time because of parantheses) and then I built a non-deterministic finite automaton (NFA) out of the evaluation tree (the NFA can be built in linear time in the size of the tree). Then, using the NFA, we can decide if a string of length L matches the initial expression or not in O(L * N), where N = the number of states of the NFA (although this is usually much faster, because the number of matched states at each step is usually much smaller than N).
The alternative would have been to turn the NFA into a deterministic finite automaton (DFA) in which case deciding if a string matches the regular expression takes only O(L) time. The drawback is that the DFA may have an exponential number of states relative to the number of states of the NFA (and even if this were not the case in this problem, building the DFA would still be algorithmically challenging).
Personally I would have expected some discussion about automata in the editorial (because that's what regex.h probably uses).