A bit of requirements engineering, lest we propose solutions that won't work given hitherto unstated requirements.

If your table contains keys "foo" and "foo_bar", how should the input string "foo bar" be handled? If "foo" is matched and replaced first, then the "foo_bar" key will never match. Is this an issue? If so, how should this case be handled? Should the solution attempt to match the longest possible string first (i.e., lookahead past "foo")?

Likewise, if your table contains keys "foo_bar" and "bar_baz", how should the input string "foo bar baz" be handled? If "foo_bar" is matched and replaced first, then "bar_baz" won't match. Is this an issue? If so, how should this case be handled?