Modelling regex replacement via a DFA
Depending on the exact semantics of the replace operation (regarding multiple matches, overlapping matches, etc.), it can likely be modelled as a finite-state transducer.  The set of possible values of s can be modelled as a regular language.  It is known that the application of a finite-state transducer to a regular language gives you another regular language, and there are standard algorithms for computing it, using the product construction.