Yes, the use of state machines seems to be required. I was wondering about more precise ideas about making it not to slow, but flexible. The problems I had were mainly to combine absolute time (speed of the combo) and precedence an elegant way, and to limite the use of saved pad datas to the minimum needed.
Do you know some articles about the subject or, maybe better, free implementations ?
One fairly obvious way is to use a tree structure. where each node represents a move and the children represent the exit conditions. Whatever structure you use doesn't have to be super-efficient, you'll only be doing one transition per input read.
I think a tree structure will not be sufficient: multiple ways might exist to go to some state. I wonder how to implement some timeout message a simple way, too (the timer test and countdown might not depend on the current state...)
I'll try to write some code and maybe write more about later.
The root node is where you start, the controller is in neutral. You then have a child node for every controller state that can start a combo from that state. From each child you have children for each state that continue a combo and so on, until you either reach a final state or until there is no child for the current controller state in which case you start again from the root. If you want to, there's nothing that prevents you from creating loops (though in that case it is no longer a tree).
Adding timing information shouldn't be too difficult either, just add a limit value to each node or to each child pointer. The limit value could tell you how long you can stay in the current state before returning to the root or for how long each child pointer is valid (or possibly use both, depending on your needs). The timer could be implemented through a timer interrupt or reading a counter - using something like vsync leads to different timings on PAL and NTSC machines.
If you need help with graphs or state machines Google or any basic comp. sci. textboox should provide more than enough info.