I was using sed to do many replacements (hundreds) in a file and it was starting to be slow, running in O(num_replacemnts). I thought that this can be done with a state machine so the runtime could be independent of the number of replacements.

I googled a bit and found this amazing gem: it uses lex to create a custom C program that does just what you want. Posix compliant. All wrapped up in bash function.